题目描述

给定一个有 $N$ 个顶点和 $N -1$条边的树。顶点从 $1$到 $N$ 编号，第$i$条边连接顶点 $a_i$和 $b_i$。

你有 $K$ 种颜色的染色材料。 对于树中的每个顶点，你要选择$K$种颜色之一来染色，使得满足以下条件:

• 如果两个不同的顶点 $x$ 和 $y$ 的距离小于等于 2，则$x$和$y$的颜色不同。

有多少种方法可以给树染色?找到结果对1000000007取模的结果。

输入

第一行两个整数$N,K$

接下来一共$N-1$行，表示第$i$条边连接的两个端点$a_i,b_i$

输出

打印给树染色的方法数量，结果对 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 \leq N,K \leq 10^5$

$1 \leq a_i,b_i \leq N$

给定的图是一颗树