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, \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: [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$;  $\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$.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(n, m, q) = map(int, input().split())
MOD = 10 ** 9 + 7
edges = []
adj = [[] for _ in range(n)]
for i in range(m):
	(a, b, w) = map(int, input().split())
	a -= 1
	b -= 1
	edges.append((a, b, w))
	adj[a].append((b, w))
	adj[b].append((a, w))
INF = 10 ** 18
ans = 0
DP = [-INF] * n
DP[0] = 0
for plen in range(m):
	NDP = [-INF] * n
	for (a, b, w) in edges:
		NDP[b] = max(NDP[b], DP[a] + w)
		NDP[a] = max(NDP[a], DP[b] + w)
	DP = NDP
	ans = (ans + max(DP)) % MOD

def convex_hull_trick(K, M, integer=True):
	if integer:
		intersect = lambda i, j: (M[j] - M[i]) // (K[i] - K[j])
	else:
		intersect = lambda i, j: (M[j] - M[i]) / (K[i] - K[j])
	assert len(K) == len(M)
	hull_i = []
	hull_x = []
	order = sorted(range(len(K)), key=K.__getitem__)
	for i in order:
		while True:
			if not hull_i:
				hull_i.append(i)
				break
			elif K[hull_i[-1]] == K[i]:
				if M[hull_i[-1]] >= M[i]:
					break
				hull_i.pop()
				if hull_x:
					hull_x.pop()
			else:
				x = intersect(i, hull_i[-1])
				if hull_x and x <= hull_x[-1]:
					hull_i.pop()
					hull_x.pop()
				else:
					hull_i.append(i)
					hull_x.append(x)
					break
	return (hull_i, hull_x)
(slope, intersect) = ([], [])
for (a, b, w) in edges:
	i = max(a, b, key=lambda i: DP[i])
	assert DP[i] > 0
	slope.append(w)
	intersect.append(DP[i])
(hull_i, hull_x) = convex_hull_trick(slope, intersect)

def tri(x):
	return x * (x + 1) // 2
lt = 0
for (i, j) in enumerate(hull_i):
	(wt, w) = (intersect[j], slope[j])
	until = min(q if i == len(hull_x) else hull_x[i], q - m)
	if until <= 0:
		continue
	active = until - lt
	ans = (ans + active * wt) % MOD
	min_uses = lt
	max_uses = lt + active
	times = tri(max_uses) - tri(min_uses)
	ans = (ans + times * w) % MOD
	lt = until
	if lt == q - m:
		break
print(ans)


(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]
		elif poss[i] == curmx and hasmxw[i]:
			ov = True
	curw = curmx
	sol += curw
	sol %= mod
	l += 1
if l == q:
	print(sol)
elif 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)


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
MOD = 10 ** 9 + 7
INF = 100

def convex_hull_trick(K, M, integer=True):
	if integer:
		intersect = lambda i, j: (M[j] - M[i]) // (K[i] - K[j])
	else:
		intersect = lambda i, j: (M[j] - M[i]) / (K[i] - K[j])
	assert len(K) == len(M)
	hull_i = []
	hull_x = []
	order = sorted(list(range(len(K))), key=K.__getitem__)
	for i in order:
		while True:
			if not hull_i:
				hull_i.append(i)
				break
			elif K[hull_i[-1]] == K[i]:
				if M[hull_i[-1]] >= M[i]:
					break
				hull_i.pop()
				if hull_x:
					hull_x.pop()
			else:
				x = intersect(i, hull_i[-1])
				if hull_x and x <= hull_x[-1]:
					hull_i.pop()
					hull_x.pop()
				else:
					hull_i.append(i)
					hull_x.append(x)
					break
	return (hull_i, hull_x)

def nn2(n):
	return n * (n + 1) // 2

def solve(n, m, q, edges):
	dp = [[-INF] * (m + 1) for _ in range(n)]
	mk = [0] * (m + 1)
	dp[0][0] = 0
	for k in range(1, m + 1):
		for e in edges:
			if dp[e[0]][k - 1] == -INF:
				continue
			dp[e[1]][k] = max(dp[e[1]][k], dp[e[0]][k - 1] + e[2])
			mk[k] = max(mk[k], dp[e[1]][k])
	ans = sum(mk) % MOD
	if q > m:
		intersect = [dp[i][m] for i in range(n)]
		slope = [0] * n
		for e in edges:
			if e[2] > slope[e[0]]:
				slope[e[0]] = e[2]
		(hull_i, hull_x) = convex_hull_trick(slope, intersect)
		lt = 0
		for (i, j) in enumerate(hull_i):
			wt = intersect[j]
			w = slope[j]
			until = min(q if i == len(hull_x) else hull_x[i], q - m)
			if until <= 0:
				continue
			active = until - lt
			ans = (ans + active * wt) % MOD
			min_uses = lt
			max_uses = lt + active
			times = nn2(max_uses) - nn2(min_uses)
			ans = (ans + times * w) % MOD
			lt = until
			if lt == q - m:
				break
	return ans

def main():
	(n, m, q) = ria()
	e = []
	for _ in range(m):
		(u, v, w) = ria()
		u -= 1
		v -= 1
		e.append((u, v, w))
		e.append((v, u, w))
	wi(solve(n, m, q, e))

def __starting_point():
	main()
__starting_point()