AT_arc093_c [ARC093E] Bichrome Spanning Tree

有一个包含 $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 \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 翻译