A 城共有 N 个通信基站通过 N-1 条光纤线路连接在一起，形成了一个没有环路的网络结构。基站编号为 1 到 N，每条光纤线路连接两个不同的基站，保证任意两个基站之间有且仅有一条路径可达。
为了优化信号传输，工程师需要为每个基站分配一种信号频段，共有 K 种不同的频段可供选择。然而，由于信号干扰的问题，分配规则要求：如果两个基站之间的距离（即它们之间最短路径上的光纤线路数量）小于或等于 2，那么这两个基站必须使用不同的信号频段，以避免干扰。
你的任务是计算出，有多少种不同的频段分配方案可以满足上述条件。由于方案数可能非常大，请将结果对 1,000,000,007 取模后输出。
第一行输入两个整数 N 和 K，分别表示通信基站的数量和可用的信号频段的种类数。
接下来的 N-1 行，每行包含两个整数 U_i 和 V_i，表示基站 U_i 和基站 V_i 之间有一条光纤线路相连。
输出一个整数，表示满足条件的频段分配方案数对 1,000,000,007 取模后的结果。
3 3 1 2 2 3
6
4 4 1 2 1 3 1 4
24
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-2-3。共有 3 种频段可供选择，假设这三种频段分别为 A、B、C，那么 1 2 3 这三个基站分别可以选择如下 6 种不同的频段分配方案。
| 基站 1 | 基站 2 | 基站 3 |
|---|---|---|
A | B | C |
A | C | B |
B | A | C |
B | C | A |
C | A | B |
C | B | A |
对于所有的测试数据有 1 \le N,K \le 10^5，1 \le U_i \neq V_i \le N。
| 测试点 | N,K | 特殊性质 |
|---|---|---|
| 1,2 | 1 \le N,K \le 30 | A |
| 3,4 | 1 \le N,K \le 30 | B |
| 5,6 | 1 \le N,K \le 100 | 无 |
| 5 \sim 25 | 1 \le N,K \le 10^5 | 无 |
特殊性质 A：保证基站网络形成一条链状结构。
特殊性质 B：保证所有的 U_i 都相同，所有的 V_i 都不同。