問題文

Penguinman は Paken 王国に住んでいます。

Paken 王国は $N$ 個の都市と $M$ 本の道路からなり、各都市には $1$ ~ $N$ までの番号が割り振られています。

$i$ 本目の道路は都市 $x_i$ と都市 $y_i$ を双方向に結び、その長さはある $2$ 以上の整数 $X$ を用いて表され、 $X^{z_i}$ です。道路の長さは互いに相異なり、具体的には任意の $i\ (1\leq i\leq M-1)$ において $z_i<z_{i+1}$ が成り立ちます。また、任意の都市から任意の都市まで幾つかの道路を経由して辿り着けることが保証されています。

Paken 王国では交通にかかる時間が問題になっており、政策の一環として全ての $i,j\ (1\leq i<j\leq N)$ の選び方における都市 $i,j$ 間の最短距離の長さの総和を求める必要が出てきました。

しかしながらデータの量は膨大で、Paken 王国の人々では求めることができませんでした。

このままだと政策が滞ってしまうので、彼らの代わりに総和を求め、 $10^9+7$ で割った余りを出力してあげてください。

入力

\(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}$
• 任意の都市から任意の都市まで幾つかの道路を使うことで移動できる
• 入力は全て整数

出力

答えを1行に出力し、最後に改行してください。

サンプル

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