题目描述

$N$ 頂点、$N-1$ 辺を持つ木が与えられます。 頂点には番号 $1,2,...,N$ がつけられており、$i$ 番目の辺は頂点 $a_i,b_i$ をつないでいます。

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

• 二つの異なる頂点 $x,y$ 間の距離が $2$ 以下ならば、頂点 $x$ の色と頂点 $y$ の色は異なる。

木を塗り分ける方法は何通りあるでしょうか。 総数を $1,000,000,007$ で割った余りを求めてください。

木とは

木とはグラフの一種です。詳しくはこちらをご覧ください: Wikipedia「木 (数学)」

距離とは

二つの頂点 $x,y$ 間の距離とは、$x$ から $y$ に到達する際にたどる必要のある最小の辺数です。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $.$ $.$ $.$ $a_{N-1}$ $b_{N-1}$

输出格式

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

题目大意

给定一个 $n$ 个节点的树。现在你拥有 $k$ 种颜色，你要用这些颜色给树上的每个节点染色，使得任何两个距离不大于 $2$ 的不同节点所被染的颜色不同。

由于答案可能过大，请将其对 $10^9+7$ 取模。

4 3
1 2
2 3
3 4

6

5 4
1 2
1 3
1 4
4 5

48

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

271414432

提示

制約

• $1\ \leqq\ N,K\ \leqq\ 10^5$
• $1\ \leqq\ a_i,b_i\ \leqq\ N$
• 与えられるグラフは木である。

Sample Explanation 1

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