当前没有测试数据。

题目描述

A城共有 $N$ 个通信基站通过 $N-1$ 条光纤线路连接在一起，形成了一个没有环路的网络结构。基站编号为 $1$ 到 $N$，每条光纤线路连接两个不同的基站，保证任意两个基站之间有且仅有一条路径可达。

为了优化信号传输，工程师需要为每个基站分配一种信号频段，共有 $K$ 种不同的频段可供选择。然而，由于信号干扰的问题，分配规则要求：如果两个基站之间的距离（即它们之间最短路径上的光纤线路数量）小于或等于 $2$，那么这两个基站必须使用不同的信号频段，以避免干扰。

你的任务是计算出，有多少种不同的频段分配方案可以满足上述条件。由于方案数可能非常大，请将结果对 $10^9+7$ 取模后输出。

输入格式

第一行输入两个整数 $N$ 和 $K$，分别表示通信基站的数量和可用的信号频段的种类数。

接下来的 $N-1$ 行，每行包含两个整数 $U_i$ 和 $V_i$，表示基站 $U_i$ 和基站 $V_i$ 之间有一条光纤线路相连。

输出格式

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

样例 #1

输入

3 3
1 2
2 3

输出

6

数据范围

对于所有的测试数据有 $1 \le N, K \le 10^5$，$1 \le U_i \neq V_i \le N$。