分数: 900 点
问题陈述
我们有一个无向加权图 N 顶点和 M 边缘。 的 i图中的第一条边连接顶点 U_i 和顶点 V_i,重量为 W_i。 另外,你会得到一个整数 X.
求出将图中每条边绘制为白色或黑色以满足以下条件的方法的数量,取模 10^9 + 7:
- 该图有一个生成树,其中包含涂成白色的边和涂成黑色的边。此外,在这些生成树中,权重最小的一棵树的权重为 X.
这里,生成树的权重是生成树中包含的边的权重之和。
约束
- 1 \leq N \leq 1 000
- 1 \leq M \leq 2 000
- 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
- 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
- If i \neq j,那么 (U_i, V_i) \neq (U_j, V_j) 和 (U_i, V_i) \neq (V_j, U_j).
- U_i \neq V_i (1 \leq i \leq M)
- 给定的图形已连接。
- 1 \leq X \leq 10^{12}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X U_1 V_1 W_1 U_2 V_2 W_2 : U_M V_M W_M
输出
打印答案。
示例输入 1
3 3 2 1 2 1 2 3 1 3 1 1
示例输出 1
6
示例输入 2
3 3 3 1 2 1 2 3 1 3 1 2
示例输出 2
2
示例输入 3
5 4 1 1 2 3 1 3 3 2 4 6 2 5 8
示例输出 3
0
示例输入 4
8 10 49 4 6 10 8 4 11 5 8 9 1 8 10 3 8 128773450 7 8 10 4 2 4 3 4 1 3 1 13 5 2 2
示例输出 4
4