s10的红黑树

众所周知，红黑树是一种优秀的数据结构，是每个节点都带有颜色属性（红色或者黑色）的二叉查找树。这道题也是关于树上的问题，但是与之不同的是，是每条边有颜色属性，其值为红色或者黑色。
现在有一棵树（无环的无向图），树上有$n$个节点，$n-1$条无向边，每条边是红色或者黑色。同时给定一个正整数$k$，我们定义序列 $a_1, a_2, …, a_k$为 "s10序列"当且仅当其满足以下条件：我们从节点$a_1$开始选择最短的路径到节点$a_2$，再从节点$a_2$开始选择最短的路径到节点$a_3$，依次类推，直到我们从节点$a_{k-1}$走到节点$a_k$。如果我们走过的所有路径中经过的边，有至少一条黑色边的话， 那么就称其为”s10序列”。（注意其中对于序列中的不同$a_i$的取值可以重复）

显然对于$n$个节点的树，给定正整数$k$，我们可以有$n^k$个序列。我们现在需要统计其中有多少序列是“S10序列”。答案可能会很大，请输出答案对1000000007取模的结果。

第一行给出一个正整数$T$，表示数据组数。
接下来对于每组数据，第一行给出两个正整数$n$和$k$，分别表示这棵树的节点个数和“S10序列”的长度。
接下来$n-1$行，每行给出三个正整数$x, y, v$，分别表示树中一条边的两个节点和边的颜色（0表示红色，1表示黑色）。

数据范围：
$k \le n \le 200000$
$1 \le x, y \le n$ ($x$ 不等于 $y$)
$v = $ $0$或$1$

对于每组数据，输出“s10序列”的数量对1000000007取模的结果。

3
4 4
1 2 1
2 3 1
3 4 1
2 2
1 2 1
3 2
1 2 1
3 2 0

252
2
4

“字节跳动杯”杭州电子科技大学2019新生编程大赛