Problem Statement

Penguinman lives in the Kingdom of Paken.

The Kingdom of Paken consists of $N$ cities and $M$ roads, and each city is assigned a number from $1$ to $N$.

The $i$-th road bidirectionally connects city $x_i$ and city $y_i$, and its length is expressed using a certain integer $X$ that is at least $2$, as $X^{z_i}$. The lengths of the roads are pairwise distinct; specifically, $z_i<z_{i+1}$ holds for every $i\ (1\leq i\leq M-1)$. It is also guaranteed that any city can be reached from any other city by traveling along some roads.

In the Kingdom of Paken, the time spent on transportation has become a problem, and as part of a policy, it has become necessary to find the sum of the shortest distances between cities $i,j$ over all choices of $i,j\ (1\leq i<j\leq N)$.

However, the amount of data is enormous, and the people of the Kingdom of Paken were unable to compute it.

Since the policy will stall if things stay as they are, please find the sum on their behalf and output the remainder when it is divided by $10^9+7$.

Input

\(N\) \(M\) \(X\)
\(x_1\) \(y_1\) \(z_1\)
\(x_2\) \(y_2\) \(z_2\)
\(︙\)
\(x_M\) \(y_M\) \(z_M\)

• $2≤N≤2×10^5$
• $N-1≤M≤2×10^5$
• $2≤X≤10^9$
• $1≤x_i,y_i≤N$
• $0≤z_i≤10^9$
• $x_i≠y_i$
• $z_i<z_{i+1}$
• Any city can be reached from any other city by using some roads
• All inputs are integers

Output

Output the answer on 1 line, followed by a newline.

Sample

3 2 3
1 2 0
2 3 1

8

5 5 5
1 4 3
2 4 4
3 5 7
2 3 8
2 3 10

2660500

6 8 1000000
2 6 10
3 5 11
4 6 23
1 3 26
1 6 30
5 6 48
3 5 88
3 6 100

524978526