J. The Messenger's Disguise
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Warring States period of ancient China, espionage was the key to survival. An agent named Lian has received a critical mission: to deliver a message from his base in Shanghai (represented on the map by vertex $$$S$$$) to an allied general in the walled city of Tianjin (vertex $$$T$$$).

Lian's spymaster warned him: "Our enemies are cunning. They know all the roads and expect an urgent messenger to use the fastest possible path. If you arrive from Shanghai to Tianjin in record time, your identity will be revealed."

The order was clear: calculate the shortest path length, $$$D$$$, but do not use it. Instead, to pass as a common merchant who might have taken a detour, you must follow a path of length exactly $$$D+1$$$.

To have flexibility and escape routes, Lian needs to know how many travel options meet this condition. Your task is to help him count the number of distinct paths from Shanghai to Tianjin with a length of precisely one more than the minimum.

Input

The first line contains four integers $$$N, M, S,$$$ and $$$T$$$ ($$$1 \leq N, M \leq 10^6, 1 \leq S \neq T \leq N$$$), representing the number of cities and roads in China, the starting vertex ($$$S$$$, Shanghai), and the destination vertex ($$$T$$$, Tianjin). The next $$$M$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i \neq v_i \leq N$$$), indicating that there is a bidirectional road between cities $$$u_i$$$ and $$$v_i$$$.

Output

Print a single integer: the number of distinct paths from Shanghai to Tianjin with a length of one more than the minimum. As this number can be very large, print the result modulo $$$10^9+7$$$.

Examples
Input
5 6 1 3
1 2
2 3
1 4
4 2
2 5
5 3
Output
2
Input
3 5 1 2
1 2
1 3
1 3
2 3
2 3
Output
4
Input
2 1 1 2
1 2
Output
0
Note

A path from Shanghai to Tianjin is guaranteed to exist. Multiple roads may exist between the same pair of cities.