该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T2 五颜六色 (color, 1s/256M)

树是一种具有 $n$ 个点 $n-1$ 条边的无向连通图。

六一儿童节快到了，老师安排你去给一棵树进行装饰，从而让其变得更好看。老师给了你 $k$ 桶染料，每一种染料的颜色都不同。你需要将这棵树染色之后尽量显得不单调，具体来说：

• 对于树上任意两个距离不超过 $2$ 的节点 $x$ 和 $y$，其所染的颜色不相同。

你想要知道：一共有多少种染色方法，可以使得这棵树满足上述条件？不一定每一种颜料都需要使用。由于答案可能会很大，请输出答案对 $10^9 + 7$ 取模之后的结果。

输入格式

第一行两个正整数 $n,k$，分别表示树的节点个数和染色颜料种数。

接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$，表示树上节点 $u_i$ 和 $v_i$ 之间有一条边。保证输入给出的是一棵树。

输出格式

输出一行一个整数，表示染色方案数，对 $10^9 + 7$ 取模后的结果。

样例输入

4 3
1 2
2 3
3 4

样例输出

6

样例解释

数据范围

• 对于 30% 的数据，$2 \le n \le 10$;
• 对于 60% 的数据，$2 \le n \le 1000$;
• 对于 100% 的数据，$2\le k \le n \le 5\cdot 10^5, 1\le u_i, v_i \le n, u_i \ne v_i$.