给定一棵包含 $N$ 个顶点的无向树。每条边都有一个长度，且长度为严格正整数。树中会出现 $M$ 辆出租车和 $M$ 位乘客，每辆出租车和每位乘客都恰好出现在一个节点上。一个节点可能包含多辆出租车和/或多位乘客。

打车软件会将乘客与出租车进行匹配。如今，乘客必须支付出租车前往接载他们所行驶的距离。该打车软件是恶意贪心的，因此它会以使出租车前往各自乘客的总行驶距离尽可能大的方式来匹配乘客与出租车。注意，每辆出租车恰好分配给一位乘客，每位乘客也恰好分配给一辆出租车。

出租车和乘客在树中出现的方式共有 $N^{2M}$ 种。对于每种方式，我们可以根据打车软件所选的恶意贪心匹配计算出出租车的总行驶距离。你的任务是将所有这些距离相加，并计算该总和对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 2500$)。

接下来的 $N-1$ 行，每行包含三个整数 $x, y$ 和 $l$。这表示在节点 $x$ 和 $y$ 之间存在一条长度为 $l$ 的无向边 ($1 \le l \le 10000$)。保证给定的边构成一棵树。

输出格式

输出一行，包含一个整数：所求总和对 $10^9 + 7$ 取模的结果。

样例

输入 1

5 2
4 5 9805
3 4 2001
2 3 6438
1 3 3790

输出 1

10784056