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 1000000007. If t cannot be reached from s at all, print -1 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

4 4
0 1 1
0 2 1
1 3 1
2 3 1
0 3

2

3 1
0 1 5
0 2

-1