[ABC133E] Virus Tree 2

给定一个 $n$ 个节点的树。现在你拥有 $k$ 种颜色，你要用这些颜色给树上的每个节点染色，使得任何两个距离不大于 $2$ 的**不同节点**所被染的颜色不同。 求染色方案数。由于答案可能过大，请将其对 $10^9+7$ 取模。

[problemUrl]: https://atcoder.jp/contests/abc133/tasks/abc133_e $ N $ 頂点、$ N-1 $ 辺を持つ木が与えられます。 頂点には番号 $ 1,2,...,N $ がつけられており、$ i $ 番目の辺は頂点 $ a_i,b_i $ をつないでいます。 あなたは $ K $ 色の絵の具を持っています。 木の頂点それぞれに対して、以下の条件を満たすように、$ K $ 色の中から $ 1 $ 色を選んで塗ることにしました。 - 二つの異なる頂点 $ x,y $ 間の距離が $ 2 $ 以下ならば、頂点 $ x $ の色と頂点 $ y $ の色は異なる。 木を塗り分ける方法は何通りあるでしょうか。 総数を $ 1,000,000,007 $ で割った余りを求めてください。 木とは 木とはグラフの一種です。詳しくはこちらをご覧ください: [Wikipedia「木 (数学)」](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6)) 距離とは 二つの頂点 $ x,y $ 間の距離とは、$ x $ から $ y $ に到達する際にたどる必要のある最小の辺数です。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ . $ $ . $ $ . $ $ a_{N-1} $ $ b_{N-1} $

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

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 !\[zu\](https://img.atcoder.jp/ghi/491cd56a53e99ba7677ee4827b8f767a.png) 塗り分け方は $ 6 $ 通りです。