Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Jog Around The Graph

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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, \dots, v_{k+1}$$$ such that for each $$$i$$$ $$$(1 \le i \le 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 \le n \le 2000$$$; $$$n - 1 \le m \le 2000$$$; $$$m \le q \le 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 \le v, u \le n$$$; $$$1 \le w \le 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, \dots, 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$$$;
- $$$\dots$$$

So the answer is the sum of $$$25$$$ terms: $$$3+11+24+39+\dots$$$

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 13:13:31 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|