Contest Duration: - (local time) (100 minutes) Back to Home
D - Number of Shortest paths /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 個の道路があります。

制約

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i) は相異なる
• 入力に含まれる値は全て整数である

入力

N M
A_1 B_1
\vdots
A_M B_M


入力例 1

4 5
2 4
1 2
2 3
1 3
3 4


出力例 1

2


入力例 2

4 3
1 3
2 3
2 4


出力例 2

1


入力例 3

2 0


出力例 3

0


入力例 4

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7


出力例 4

4


Score : 400 points

Problem Statement

The Republic of AtCoder has N cities numbered 1 through N and M roads numbered 1 through M.

Using Road i, you can travel from City A_i to B_i or vice versa in one hour.

How many paths are there in which you can get from City 1 to City N as early as possible?
Since the count can be enormous, print it modulo (10^9 + 7).

Constraints

• 2 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• The pairs (A_i, B_i) are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M


Output

Print the answer. If it is impossible to get from City 1 to City N, print 0.

Sample Input 1

4 5
2 4
1 2
2 3
1 3
3 4


Sample Output 1

2


The shortest time needed to get from City 1 to City 4 is 2 hours, which is achieved by two paths: 1 \to 2 \to 4 and 1 \to 3 \to 4.

Sample Input 2

4 3
1 3
2 3
2 4


Sample Output 2

1


The shortest time needed to get from City 1 to City 4 is 3 hours, which is achieved by one path: 1 \to 3 \to 2 \to 4.

Sample Input 3

2 0


Sample Output 3

0


It is impossible to get from City 1 to City 2, in which case you should print 0.

Sample Input 4

7 8
1 3
1 4
2 3
2 4
2 5
2 6
5 7
6 7


Sample Output 4

4