A town is a weighted undirected graph of n squares (numbered 0 to n-1) joined by m streets, each with a positive integer length. A route is a path that starts at square s, ends at square t, and never revisits a square.
Among all routes from s to t, consider those whose total length equals the minimum possible (the shortest-path distance from to ). Count how many such minimum-length routes exist, and report the count modulo . If is unreachable from , the count is . If equals , there is exactly one route (the empty route), so the count is .
Because all street lengths are positive, every minimum-length route is automatically a simple path (no repeated square).
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a street between squares u and v of length w.
Final line: two integers s t.
Output format
A single integer: the number of distinct shortest (minimum-total-length) routes from s to t, modulo 1000000007.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= s, t, u, v <= n-1
- 1 <= w <= 1000000