1366_F. 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:

<image>

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.
```python
import sys
n,m,q=map(int,input().split())
mod,mxw = 1000000007,0;wgts,neig=[0]*n,[0]*n
for i in range(n):
    neig[i]=[0]

for i in range(m):
    a,b,w=map(int,input().split())
    a-=1;b-=1;neig[a][0]+=1;neig[b][0]+=1;neig[a].append([b,w]);neig[b].append([a,w])
    mxw=max(mxw,w);wgts[a]=max(wgts[a],w);wgts[b]=max(wgts[b],w)
poss=[-1]*n;poss[0]=0;sol=0;curw=0;hasmxw=[False]*n
for i in range(n):
    if wgts[i]==mxw:hasmxw[i]=True
ov=False;l=0
while l<q and not ov and l<3000:
    newposs=[-1]*n;curmx=0
    for i in range(n):
        if poss[i]>=0:
            for j in range(1,neig[i][0]+1):newposs[neig[i][j][0]]=max(newposs[neig[i][j][0]],poss[i]+neig[i][j][1])    
    for i in range(n):
        poss[i]=newposs[i]
        if poss[i]>curmx:curmx=poss[i];ov=hasmxw[i]
        else:
            if poss[i]==curmx and hasmxw[i]:ov=True
    curw=curmx;sol+=curw;sol%=mod;l+=1
if l==q:print(sol)
else:
    if ov:rem=q-l;sol+=rem*curw;sol%=mod;sol+=mxw*((rem*(rem+1))//2);sol%=mod;print(sol)
    else:
        rem=q-l
        while not ov:
            mx=0;gd=-1
            for i in range(n):
                if poss[i]==curw:mx=max(mx,wgts[i])            
            for i in range(n):
                if wgts[i]>mx and poss[i]>=0:
                    diff=wgts[i]-mx;loss=curw-poss[i];loss+=diff-1;att=loss//diff
                    if gd==-1:gd=att
                    gd=min(att,gd)
            if gd==-1 or gd>rem:sol+=rem*curw;sol+=mx*((rem*(rem+1))//2);sol%=mod;ov=True
            else:
                sol+=(gd-1)*curw;sol+=mx*((gd*(gd-1))//2);sol%=mod
                for i in range(n):poss[i]+=gd*wgts[i];curw=max(curw,poss[i])
                sol+=curw;rem-=gd
        print(sol)
```