题目描述

给定一棵 $n$ 个点的无根树，点的编号为 $1$ 到 $n$，边的边权均为 $n$ 的正整数次幂。 定义 $u$ 到 $v$ 的距离 $\operatorname{d(u,v)}$ 为 $u$ 和 $v$ 在树上的简单路径经过的边的边权之和。

给定 $k$，请在 $\dfrac{n\times (n-1)}{2}$ 个 $\operatorname{d(u,v)}(1\le u<v\le n)$ 中找到第 $k$ 小的值。

输入格式

第一行两个正整数 $n,k$。

接下来 $n-1$ 行，每行三个正整数 $x,y,z(1\le x,y,z\le n)$，表示一条连接 $x$ 和 $y$ 的树边，其边权为 $n$ 的 $z$ 次方。

输出格式

输出一行一个整数，即第 $k$ 小的值对 $10^9+7$ 取模的结果。

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

135

提示

对于 $100\%$ 的数据，$2\le n\le 2.5\times 10^4$，$1\le k\le \dfrac{n*(n-1)}{2}$。

样例解释：

所有的 $d$ 排序后依次为： $5,5,25,30,125,130,130,135,150,155$。