给你一棵由 $$$n$$$ 个顶点组成的树(一个无环的连通无向图)。树的每条 $$$n - 1$$$ 边都涂成黑色或红色。
您还获得了一个整数 $$$k$$$。考虑 $$$k$$$ 顶点的序列。如果序列 $$$[a_1, a_2, \ldots, a_k]$$$ 满足以下条件,我们称其为好序列:
- 我们将在树上行走一条路径(可能多次访问相同的边/顶点),从 $$$a_1$$$ 开始,到 $$$a_k$$$ 结束。
- 从 $$$a_1$$$ 开始,然后使用 $$$a_1$$$ 和 $$$a_2$$$ 之间的最短路径前往 $$$a_2$$$,然后以类似的方式前往 $$$a_3$$$,依此类推,直到走完 $$$a_{k-1}$$$ 和 $$$a_k$$$ 之间的最短路径。
- 如果在此过程中您至少走过一个黑色边缘,则序列良好。
考虑图片上的树。如果 $$$k=3$$$ 则以下序列是好的:$$$[1, 4, 7]$$$、$$$[5, 5, 3]$$$ 和 $$$[2, 3, 7]$$$。以下序列不好:$$$[1, 4, 6]$$$、$$$[5, 5, 5]$$$、$$$[3, 7, 3]$$$。
有 $$$n^k$$$ 个顶点序列,计算其中有多少个是好的。由于这个数字可能非常大,因此打印它对 $$$10^9+7$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$2 \le k \le 100$$$)、树的大小和顶点序列的长度。
接下来的 $$$n - 1$$$ 行包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$x_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$x_i \in \{0, 1\}$$$),其中 $$$u_i$$$ 和$$$v_i$$$ 表示相应边的端点,$$$x_i$$$ 是该边的颜色($$$0$$$ 表示红色边,$$$1$$$ 表示黑色边)。
输出
打印以 $$$10^9 + 7$$$ 为模的好序列数。
示例
输入 #1
4 4 1 2 1 2 3 1 3 4 1
输出 #1
252
输入 #2
4 6 1 2 0 1 3 0 1 4 0
输出 #2
0
输入 #3
3 5 1 2 1 2 3 0
输出 #3
210
注意
在第一个示例中,长度为 $$$4$$$ 的所有序列 ($$$4^4$$$) 都很好,但以下序列除外:
- $$$[1, 1, 1, 1]$$$
- $$$[2, 2, 2, 2]$$$
- $$$[3, 3, 3, 3]$$$
- $$$[4, 4, 4, 4]$$$
在第二个示例中,所有边缘都是红色,因此没有任何好的序列。