题目描述

在一座只有树形道路网的城市里，调度员 Livia 正在测试一款非常“不体贴”的打车系统。

这座城市有 $N$ 个路口，路口之间由 $N-1$ 条无向道路相连，任意两个路口之间恰好有一条简单路径。每条道路都有一个正整数长度。

某一天，会有 $M$ 辆出租车和 $M$ 名乘客出现在这些路口上。每一辆出租车、每一名乘客都会独立选择一个路口出现；同一个路口可以同时出现多辆出租车，也可以同时出现多名乘客。

系统需要把每名乘客匹配给恰好一辆出租车，同时每辆出租车也恰好服务一名乘客。乘客需要支付出租车空驶到自己所在路口的距离，而这套系统偏偏会选择一种匹配方式，使得所有出租车空驶距离之和尽可能大。

一共有 $N^{2M}$ 种出租车和乘客出现方式。对于每一种方式，都可以计算出系统选出的最大总空驶距离。请你求出所有出现方式对应的最大总空驶距离之和，并对 $10^9+7$ 取模。

输入格式

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

接下来 $N-1$ 行，每行包含三个整数 $x,y,l$，表示路口 $x$ 与路口 $y$ 之间有一条长度为 $l$ 的无向道路。

保证给出的道路构成一棵树。

输出格式

输出一行一个整数，表示所有出现方式的答案之和对 $10^9+7$ 取模后的结果。

数据范围

• $1\le N,M\le 2500$；
• $1\le l\le 10000$。

样例 1

输入

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

输出

10784056