Jog Around The Graph

You are given a simple weighted connected undirected graph, consisting of n vertices and m edges.

A path in the graph of length k is a sequence of k+1 vertices v_1, v_2, ..., v_{k+1} such that for each i (1 ≤ i ≤ k) the edge (v_i, v_{i+1}) is present in the graph. A path from some vertex v also has vertex v_1=v. Note that edges and vertices are allowed to be included in the path multiple times.

The weight of the path is the total weight of edges in it.

For each i from 1 to q consider a path from vertex 1 of length i of the maximum weight. What is the sum of weights of these q paths?

Answer can be quite large, so print it modulo 10^9+7.

Input

The first line contains a three integers n, m, q (2 ≤ n ≤ 2000; n - 1 ≤ m ≤ 2000; m ≤ q ≤ 10^9) — the number of vertices in the graph, the number of edges in the graph and the number of lengths that should be included in the answer.

Each of the next m lines contains a description of an edge: three integers v, u, w (1 ≤ v, u ≤ n; 1 ≤ w ≤ 10^6) — two vertices v and u are connected by an undirected edge with weight w. The graph contains no loops and no multiple edges. It is guaranteed that the given edges form a connected graph.

Output

Print a single integer — the sum of the weights of the paths from vertex 1 of maximum weights of lengths 1, 2, ..., q modulo 10^9+7.

Examples

Input

7 8 25 1 2 1 2 3 10 3 4 2 1 5 2 5 6 7 6 4 15 5 3 1 1 7 3

Output

4361

Input

2 1 5 1 2 4

Output

60

Input

15 15 23 13 10 12 11 14 12 2 15 5 4 10 8 10 2 4 10 7 5 3 10 1 5 6 11 1 13 8 9 15 4 4 2 9 11 15 1 11 12 14 10 8 12 3 6 11

Output

3250

Input

5 10 10000000 2 4 798 1 5 824 5 2 558 4 1 288 3 4 1890 3 1 134 2 3 1485 4 5 284 3 5 1025 1 2 649

Output

768500592

Note

Here is the graph for the first example:

Some maximum weight paths are:

• length 1: edges (1, 7) — weight 3;
• length 2: edges (1, 2), (2, 3) — weight 1+10=11;
• length 3: edges (1, 5), (5, 6), (6, 4) — weight 2+7+15=24;
• length 4: edges (1, 5), (5, 6), (6, 4), (6, 4) — weight 2+7+15+15=39;
• ...

So the answer is the sum of 25 terms: 3+11+24+39+...

In the second example the maximum weight paths have weights 4, 8, 12, 16 and 20.

inputFormat

Input

The first line contains a three integers n, m, q (2 ≤ n ≤ 2000; n - 1 ≤ m ≤ 2000; m ≤ q ≤ 10^9) — the number of vertices in the graph, the number of edges in the graph and the number of lengths that should be included in the answer.

Each of the next m lines contains a description of an edge: three integers v, u, w (1 ≤ v, u ≤ n; 1 ≤ w ≤ 10^6) — two vertices v and u are connected by an undirected edge with weight w. The graph contains no loops and no multiple edges. It is guaranteed that the given edges form a connected graph.

outputFormat

Output

Print a single integer — the sum of the weights of the paths from vertex 1 of maximum weights of lengths 1, 2, ..., q modulo 10^9+7.

Examples

Input

7 8 25 1 2 1 2 3 10 3 4 2 1 5 2 5 6 7 6 4 15 5 3 1 1 7 3

Output

4361

Input

2 1 5 1 2 4

Output

60

Input

15 15 23 13 10 12 11 14 12 2 15 5 4 10 8 10 2 4 10 7 5 3 10 1 5 6 11 1 13 8 9 15 4 4 2 9 11 15 1 11 12 14 10 8 12 3 6 11

Output

3250

Input

5 10 10000000 2 4 798 1 5 824 5 2 558 4 1 288 3 4 1890 3 1 134 2 3 1485 4 5 284 3 5 1025 1 2 649

Output

768500592

Note

Here is the graph for the first example:

Some maximum weight paths are:

• length 1: edges (1, 7) — weight 3;
• length 2: edges (1, 2), (2, 3) — weight 1+10=11;
• length 3: edges (1, 5), (5, 6), (6, 4) — weight 2+7+15=24;
• length 4: edges (1, 5), (5, 6), (6, 4), (6, 4) — weight 2+7+15+15=39;
• ...

So the answer is the sum of 25 terms: 3+11+24+39+...

In the second example the maximum weight paths have weights 4, 8, 12, 16 and 20.

样例

15 15 23
13 10 12
11 14 12
2 15 5
4 10 8
10 2 4
10 7 5
3 10 1
5 6 11
1 13 8
9 15 4
4 2 9
11 15 1
11 12 14
10 8 12
3 6 11

3250