题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的带权无向图。第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$，权值为 $W_i$。此外，给定一个整数 $X$。

请计算有多少种方法可以将该图的每一条边涂成白色或黑色，使得满足以下条件，并将答案对 $10^9+7$ 取模：

• 存在一棵同时包含白色边和黑色边的生成树，并且所有满足条件的生成树中，权值最小的那一棵的权值恰好为 $X$。

这里，生成树的权值指的是该生成树所包含的所有边的权值之和。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$ $X$
$U_1$ $V_1$ $W_1$
$U_2$ $V_2$ $W_2$
$\vdots$
$U_M$ $V_M$ $W_M$

输出格式

输出答案。

样例 1

输入

3 3
2
1 2 1
2 3 1
3 1 1

输出

6

样例 2

输入

3 3
3
1 2 1
2 3 1
3 1 2

输出

2

样例 3

输入

5 4
1
1 2 3
1 3 3
2 4 6
2 5 8

输出

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

说明/提示

限制条件

• $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$）
• 当 $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}$
• 所有输入值均为整数。

由 ChatGPT 4.1 翻译