日语版： 問題文 N N 頂点、 N − 1 N−1 辺を持つ木が与えられます。 頂点には番号 1 , 2 , . . . , N 1,2,...,N がつけられており、 i i 番目の辺は頂点 a i , b i a i ​ ,b i ​ をつないでいます。

あなたは K K 色の絵の具を持っています。 木の頂点それぞれに対して、以下の条件を満たすように、 K K 色の中から 1 1 色を選んで塗ることにしました。

二つの異なる頂点 x , y x,y 間の距離が 2 2 以下ならば、頂点 x x の色と頂点 y y の色は異なる。 木を塗り分ける方法は何通りあるでしょうか。 総数を 1 , 000 , 000 , 007 1,000,000,007 で割った余りを求めてください。

木とは 距離とは 制約 1 ≦ N , K ≦ 10 5 1≦N,K≦10 5

1 ≦ a i , b i ≦ N 1≦a i ​ ,b i ​ ≦N 与えられるグラフは木である。 入力 入力は以下の形式で標準入力から与えられます。

N N K K

a 1 a 1 ​

b 1 b 1 ​

a 2 a 2 ​

b 2 b 2 ​

. .

. .

. .

a N − 1 a N−1 ​

b N − 1 b N−1 ​

出力 木の塗り分け方の総数を 1 , 000 , 000 , 007 1,000,000,007 で割った余りを出力してください。

输入数据 1 4 3 1 2 2 3 3 4 输出数据 1 6 zu

塗り分け方は 6 6 通りです。

输入数据 2 5 4 1 2 1 3 1 4 4 5 输出数据 2 48 输入数据 3 16 22 12 1 3 1 4 16 7 12 6 2 2 15 5 16 14 16 10 11 3 10 3 13 8 6 16 8 9 12 4 3