CF1139C.Edgy Trees

You are given a tree (a connected undirected graph without cycles) of $n$ vertices. Each of the $n - 1$ edges of the tree is colored in either black or red.

You are also given an integer $k$. Consider sequences of $k$ vertices. Let's call a sequence $[a_1, a_2, \ldots, a_k]$ good if it satisfies the following criterion:

• We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from $a_1$ and ending at $a_k$.
• Start at $a_1$, then go to $a_2$ using the shortest path between $a_1$ and $a_2$, then go to $a_3$ in a similar way, and so on, until you travel the shortest path between $a_{k-1}$ and $a_k$.
• If you walked over at least one black edge during this process, then the sequence is good.

Consider the tree on the picture. If $k=3$ then the following sequences are good: $[1, 4, 7]$, $[5, 5, 3]$ and $[2, 3, 7]$. The following sequences are not good: $[1, 4, 6]$, $[5, 5, 5]$, $[3, 7, 3]$.

There are $n^k$ sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo $10^9+7$.

给你一棵树（一个无环的连通无向图），该树包含 $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_2$ 与 $a_3$ 之间的最短路径走到 $a_3$；以此类推，直至沿 $a_{k-1}$ 与 $a_k$ 之间的最短路径走到 $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$ 取模的结果。

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $2 \le k \le 100$), the size of the tree and the length of the vertex sequence.

Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$ and $x_i$ ($1 \le u_i, v_i \le n$, $x_i \in {0, 1}$), where $u_i$ and $v_i$ denote the endpoints of the corresponding edge and $x_i$ is the color of this edge ($0$ denotes red edge and $1$ denotes black edge).

第一行包含两个整数 $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$ 表示黑色边）。

Print the number of good sequences modulo $10^9 + 7$.

输出好序列的数量对 $10^9 + 7$ 取模的结果。

In the first example, all sequences ($4^4$) of length $4$ except the following are good:

• $[1, 1, 1, 1]$
• $[2, 2, 2, 2]$
• $[3, 3, 3, 3]$
• $[4, 4, 4, 4]$

In the second example, all edges are red, hence there aren't any good sequences.

在第一个例子中，所有长度为 $4$ 的序列（共 $4^4$ 个）中，除了以下序列外，其余均为好序列：

• $[1, 1, 1, 1]$
• $[2, 2, 2, 2]$
• $[3, 3, 3, 3]$
• $[4, 4, 4, 4]$

在第二个例子中，所有边均为红色，因此不存在好序列。