Distinct fastest routes: hints, no solution

A transit network has n stations numbered from 0 to n - 1. Each row of links is a two-way connection between two different stations, and no pair of stations is listed twice. Every connection is one stop.

A route is a sequence of stations from origin to target where consecutive stations are linked. A fastest route uses the minimum possible number of connections. Two routes are different if their sequences of stations differ.

Return how many different fastest routes exist from origin to target, modulo 1000000007. If origin equals target there is exactly one route of length zero, so return 1. If target cannot be reached, return 0.

Examples

Input

n = 4, links = [[0, 1], [0, 2], [1, 3], [2, 3]], origin = 0, target = 3

Output

2

Note

Both 0-1-3 and 0-2-3 take two stops.

Input

n = 9, links = [[0, 1], [0, 3], [1, 2], [1, 4], [2, 5], [3, 4], [3, 6], [4, 5], [4, 7], [5, 8], [6, 7], [7, 8]], origin = 0, target = 8

Output

6

Note

On a 3 by 3 grid of stations there are six equally short routes from one corner to the opposite corner.

Input

n = 4, links = [[0, 1], [1, 2]], origin = 0, target = 3

Output

0

Note

Station 3 is on its own, so no route exists.

Constraints

• 1 <= n <= 50000
• 0 <= links.length <= 50000
• No link joins a station to itself and no pair is repeated
• The count can be huge, so return it modulo 1000000007

Hint 1: a nudge

Suppose you already knew how many fastest routes reach each station that is one stop closer to the origin than a given station. How would that tell you the count for the station itself?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing