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