F. Night Ride
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long night of partying in Atlanta, Michael needed to get back to his hotel to meet with the rest of the officers. Luckily, MagiCorp's CEO, Magikarp, decided to deploy their driverless car system, Laymo, to Atlanta just a few days ago. Seeing this opportunity to try this out for himself, Michael called one, hoping to get a smooth ride back. However, the confusing road layouts have gotten Laymo's cars a little confused. Instead of driving regularly, all the Laymo cars now drive randomly.

The streets of Atlanta can be modeled as a graph with nodes representing intersections and edges representing two-way streets between different intersections, where the $$$i$$$-th street takes $$$t_i$$$ minutes to drive through. In total, there are $$$n$$$ intersections and $$$m$$$ streets. There can be more than 1 street between a pair of intersections.

Currently, Michael is at intersection $$$1$$$, and his hotel is at intersection $$$n$$$. Initially, his Laymo will choose a road connected to intersection $$$1$$$ uniformly at random and drive in that direction. Upon reaching the next intersection, the Laymo will again choose a road connected to that intersection uniformly at random to drive through (including the road that the Laymo just came from). This process repeats until Michael reaches his hotel, in which case he steps out of the car and stops travelling. If an intersection has no roads connected to it, the Laymo will simply stop where it is.

After $$$k$$$ minutes have passed, what is the probability that Michael will be back at the hotel with the UTPC team?

Input

The first line contains $$$n$$$, $$$m$$$, and $$$k$$$ $$$(2\leq n\leq 50, 0\leq m\leq 10^5, 1\leq k\leq 10^6)$$$ — the number of intersections, the number of streets, and the number of minutes.

The next $$$m$$$ lines contain 3 integers $$$u_i$$$, $$$v_i$$$, and $$$t_i$$$, denoting two intersections connected by a street that takes $$$t_i$$$ minutes to drive through $$$(1\leq u_i,v_i\leq n, 1\leq t_i\leq 5, u_i\neq v_i)$$$.

Output

Output a single integer, the probability that Michael will be at the hotel after $$$k$$$ minutes, modulo $$$10^9+7$$$.

Formally, let $$$M=10^9+7$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv 0 \pmod{M}$$$. Output the integer equal to $$$p\cdot q^{-1} \bmod{M}$$$. In other words, output such an integer $$$x$$$ such that $$$0\leq x \lt M$$$ and $$$x\cdot q\equiv p \pmod{M}$$$

Examples
Input
3 3 2
1 2 1
2 3 2
1 3 1
Output
500000004
Input
4 3 4
1 2 1
1 3 5
1 4 1
Output
444444448
Note

For the first test case:

At the start of the first minute, Michael goes to intersection 3 (the hotel) with probability $$$\frac{1}{2}$$$ and intersection 2 with probability $$$\frac{1}{2}$$$, and each road takes a minute to travel.

At the start of the second minute, Michael could be at the hotel, in which he exits the Laymo and stops traveling, or at intersection 2. If he is at intersection 2, Michael will go towards intersection 1 with probability $$$\frac{1}{2}$$$ and the hotel with probability $$$\frac{1}{2}$$$. However, the road to the hotel takes 2 minutes, so he will not reach the hotel in time by the end of the second minute.

In total, Michael has a $$$\frac{1}{2}$$$ probability of getting to his hotel. This is equivalent to $$$500000004$$$ (mod $$$10^9+7$$$).