Problem Statement

We have an undirected weighted graph with $N$ vertices and $M$ edges. The $i$-th edge in the graph connects Vertex $U_i$ and Vertex $V_i$, and has a weight of $W_i$. Additionally, you are given an integer $X$.

Find the number of ways to paint each edge in this graph either white or black such that the following condition is met, modulo $10^9 + 7$:

• The graph has a spanning tree that contains both an edge painted white and an edge painted black. Furthermore, among such spanning trees, the one with the smallest weight has a weight of $X$.

Here, the weight of a spanning tree is the sum of the weights of the edges contained in the spanning tree.

Constraints

• $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$, then $(U_i, V_i) \neq (U_j, V_j)$ and $(U_i, V_i) \neq (V_j, U_j)$.
• $U_i \neq V_i$ ($1 \leq i \leq M$)
• The given graph is connected.
• $1 \leq X \leq 10^{12}$
• All input values are integers.

Input

Input is given from Standard Input in the following format:

N M
X
U_1 V_1 W_1
U_2 V_2 W_2
:
U_M V_M W_M

Output

Print the answer.