题目描述

有 $N$ 个结点和 $N-1$ 条边，构成一棵树。现有 $K$ 种频段，需要为每个结点选择一种频段。树上任意两个距离不超过 $2$ 的结点不能使用相同频段。两个结点之间的距离是它们之间路径上的边数。

请计算满足条件的频段分配方案数，并对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $N,K$。

接下来 $N-1$ 行，每行包含两个整数 $U_i,V_i$，表示树上的一条边。

输出格式

输出一个整数，表示满足条件的方案数对 $10^9+7$ 取模后的结果。

样例

3 3
1 2
2 3

6

数据范围与提示

• $1\le N,K\le10^5$
• $1\le U_i,V_i\le N$，且 $U_i\ne V_i$
• 输入的边保证构成一棵树