A metro map is a simple undirected graph on n stations numbered 1 through n (no self-loops, and each pair of stations is joined by at most one track). Every track has the same length. A shortest route from station s to station t is a route using the fewest tracks.
Count how many distinct shortest routes go from station s to station t, and report that count modulo 1000000007. Two routes are distinct if their sequences of stations differ. If t cannot be reached from s, report 0. It is guaranteed that s and t are different stations.
Input format
Line 1: two integers n and m.
Next m lines: two integers u and v, a track between stations u and v.
Last line: two integers and (with ).
Output format
A single integer: the number of shortest routes from s to t, modulo 1000000007.
Constraints
- 2 <= n <= 100000
- 0 <= m <= 200000
- The graph is simple (no self-loops, no repeated track between the same pair).
- 1 <= u, v, s, t <= n and s != t