410726: GYM104094 B GPS Hack

Denis is a student and he's failed his data security exam, so today he's having a retake. He woke up late and decided to take a taxi.

Denis lives in a city, which can be represented as $$$n$$$ crossroads connected by $$$m$$$ bidirectional roads. For every road it is known, how much it takes to drive along it. Denis lives near a crossroad with number $$$s$$$ and the university is near crossroad $$$t$$$. As soon as the taxi is near the university, Denis immediately leaves it and rushes for his exam.

Unfortunately, everything is a bit more complicated — hackers had hacked a GPS in Denis's taxi. When the GPS works properly, it helps you to reach your destination as fast, as it's possible. On every crossroad it shows, which road should be taken in order to finish your journey in the fastest way. If there are more than one possible road, GPS can show you any. Hackers can make GPS show you any road they want, but no more than once.

Denis doesn't remember exactly, how did he get to the university, but he remembers the time $$$L$$$ the road took. It turned out that his teacher had already known about the attack on GPS, so he asked Denis to calculate the number of different possible routes from his place to the university as a part of his retake.

Help Denis calculate the number of routes from crossroad $$$s$$$ to crossroad $$$t$$$, that took $$$L$$$ time and were possible considering the GPS hack. As this number might be very large, find it modulo $$$10^9 + 7$$$.

The first line contains two integers $$$n$$$ and $$$m$$$ — number of crossroads and roads between them in the city, where Denis lives ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq \min{(2 \cdot 10^5, \frac{n(n - 1)}{2})}$$$).

The second line contains three integers $$$s$$$, $$$t$$$ and $$$L$$$ — crossroad number, where Denis lives, number of the crossroad near the university and the ride time ($$$1 \leq s, t \leq n$$$, $$$s \neq t$$$, $$$1 \leq L \leq 2 \cdot 10^{14}$$$).

The next $$$m$$$ lines contain descriptions of roads between crossroads. The description contains three integers $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \leq v, u \leq n$$$, $$$v \neq u$$$, $$$1 \leq w \leq 10^9$$$) — numbers of the two crossroads connected by this road and the time, needed to drive along it.

All the roads are bidirectional, any pair of crossroads is connected with no more than one road. No roads connect a crossroad with itself. It is guaranteed that it is possible to get from crossroad $$$s$$$ to the crossroad $$$t$$$.

Print the only integer — number of routes Denis could have modulo $$$10^9 + 7$$$.

6 7
1 6 12
1 2 2
1 3 4
2 5 2
3 5 4
2 4 4
4 6 6
5 6 4

4