在 Bitocja，有 $n$ 座城市，由 $n-1$ 条双向道路连接，且任意两座城市之间均可互相到达。每条道路最初都有一个通行税，税额在 $1$ 到 $n$ 比托拉（bitolar）之间。在两座城市 $a$ 和 $b$ 之间行驶，需要支付路径上所有道路的通行税之和。

Bitobajtan 国王即位后，决定将每条道路的通行税呈指数级增长！现在，一条原始通行税为 $p$ 比托拉的道路，其通行税变为 $n^p$ 比托拉。

Bitobajtan 要求顾问计算出所有 $\frac{n(n-1)}{2}$ 对不同城市之间的最小旅行成本，并将这些结果按非递减顺序排列。现在，你需要找出这份报告中第 $k$ 小的旅行成本。由于结果可能非常大，你只需要输出该成本对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 25\,000$, $1 \le k \le \frac{n(n-1)}{2}$)，分别表示 Bitocja 的城市数量和 Bitobajtan 的查询。

接下来的 $n-1$ 行，每行包含三个整数 $a_i, b_i$ 和 $p_i$ ($1 \le a_i, b_i, p_i \le n, a_i \neq b_i$)，表示在城市 $a_i$ 和 $b_i$ 之间存在一条通行税为 $n^{p_i}$ 比托拉的道路。

题目保证道路布局使得任意两座城市之间均可到达。

输出格式

输出一个整数，表示第 $k$ 小的旅行成本对 $10^9 + 7$ 取模后的结果。

样例

样例输入 1

5 8
1 2 1
3 1 3
3 4 1
5 3 2

样例输出 1

135

说明 1

所有可能的路径通行税按非递减顺序排列为：$5, 5, 25, 30, 125, 130, 130, 135, 150$ 和 $155$ 比托拉。因此，第 $8$ 小的费用为 $135 = 5^1 + 5^3 + 5^1$ 比托拉；这是从城市 $2$ 到城市 $4$ 所需支付的税额。整条路径为 $(2, 1, 3, 4)$。

子任务

在某些测试组中，对于所有的 $i$ 均满足 $p_i \le 4$。

此外，保证每个测试用例至少满足以下条件之一： $n \le 10^4$ 时间限制为 $12$ 秒（注：所有测试的时间限制统一设为 $12$ 秒）。