大致题意：

完美序列的定义：

• $a_x \to a_y$ 为最短路径
• $a_1 \to a_2 \to ... \to a_k$ 中至少经过一条黑边

给你一颗无根树，其中有黑边和红边，求该树中完美序列的数量。

输入：

输入两个正整数 $n,k$，其中 $n$ 表示无根数的节点数量，$k$ 是一个完美序列的长度（见上）

接下来 $n-1$ 行 $u_i,v_i,d_i$ 分别表示一条边与这条边的颜色，$d_i=0$ 是红色，$d_i=1$ 是黑色

输出：

完美序列的数量对 $10^9+7$ 取模

样例

样例输入

4 4
1 2 1
2 3 1
3 4 1

样例输出

252

数据范围

对于 $100\%$ 的数据：

• $1 \le n,k \le 10^5$
• $1 \le u_i,v_i \le n$
• $d_i \in 1,0$