题目描述

给一个无根树，$n$个顶点，每条边或为红或为黑。

给一个整数$k$。

对于一个$k$个顶点的序列，如果它满足下列条件称为$good$：

我们从$a_1$到$a_k$走一条路径（途经点可以重复）

从$a_1$到$a_2$走的是$a_1$到$a_2$的最短路径，$a_2$到$a_3$……$a_{k-1}$到$a_k$。

如果走过了至少一个黑边则为$good$。

输入格式

输入$n$和$k$，

下面$n-1$行包含三个整数$u_i$，$v_i$，$x_i$，表示一条边的两个顶点和它的颜色（$0$为红，$1$为黑）。

输出格式

输出$good$序列的次数$\%1000000007$。

4 4
1 2 1
2 3 1
3 4 1

252

4 6
1 2 0
1 3 0
1 4 0

0

3 5
1 2 1
2 3 0

210

数据范围

$2 \le n \le 10^5$, $2 \le k \le 100$