A courier network has n depots, numbered 0 to n - 1, connected by m two-way roads.
Road i connects depots u and v and takes w minutes to travel. Multiple roads between the same
pair of depots may exist; each is a different road even if it connects the same two depots, so using a
different road counts as a different route even between an identical pair of stops.
A route from a starting depot s to a destination depot t (with s != t) is a sequence of roads
that never visits the same depot twice. Among all routes from s to t, consider only the ones with
the minimum possible total travel time. Print how many such fastest routes exist, modulo
. If cannot be reached from at all, print instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- an undirected road between depots u and v taking w
minutes (depots are 0-indexed).
Last line: two integers s t.
Output format
A single integer: the number of fastest routes from s to t, modulo 1000000007, or -1 if t is
unreachable from s.
Constraints
- 2 <= n <= 1000
- 0 <= m <= 4000
- 0 <= u, v < n, u != v
- 1 <= w <= 1000
- 0 <= s, t < n, s != t