Score : $400$ points

问题描述

在AtCoder共和国，有编号为$1$至$N$的$N$个城市和编号为$1$至$M$的$M$条道路。

通过第$i$号道路，可以在一小时内从城市$A_i$到达城市$B_i$或反之亦然。

请问从城市$1$尽可能早地到达城市$N$有多少种路径？
由于计数结果可能非常巨大，请输出模$(10^9 + 7)$后的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:25:56