题目描述

我们有一个无向加权图，有 $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$）
• 若 $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