有一颗$N$个结点的树，$N-1$条边，节点编号$1$到$N$,第$i$条边连接节点$a[i]$和$b[i]$。有$K$种颜色，对于每个节点，选用一种颜色涂色，目的要满足以下条件:如果两个节点的距离小于等于$2$，则它们的节点不得相同，问这棵树与多少种合法的涂色方案？答案对$10^9+7$去摸后输出。

输入

第一行两个整数$N$和$K$。接下来$N-1$行，每行两个整数，表示$a[i]$和$b[i]$

样例输入#1

4 3

1 2

2 3

3 4

4 5

样例输出#1

6

$1<=N,K<=10^5$

$1<=a[i],b[i]<=N$