Description

小J占山为王有一段时间了，他决定把自己的地盘打扮一下---将各种颜色的旗插在山头上

当然某一座的山头只能用一种颜色的旗。

整个地盘有N个山头，可看成是一棵有N个节点的树。

小J还是有一点艺术细胞的，他不想整个地盘杂乱无章。

于是他规定手下，如果某两座山之间的距离<=2的话，则这两座山不能用同一种颜色的旗

小J一共采购了ｘ种颜色的旗。

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

Format

Input

第一行一个数n,k，含义如题

接下来共有n-1行，两个数u,v表示u和v之间存在一条边

1≤n,x≤1e5,

Output

如题

Samples

4 3
1 2
2 3
3 4

6