D - 最短路径的数量

得分: $400$ 分

问题描述

在AtCoder共和国里有 $N$ 个城市，标号从 $1$ 到 $N$，有 $M$ 条道路，标号从 $1$ 到 $M$。

你可以通过第 $i$ 条道路，以一个小时的时间从城市 $A_i$ 去往城市 $B_i$ 或者反过来。

有多少种路径可以使你尽快地从城市 $1$ 到城市 $N$？
由于数量可能非常大，输出它除以 $(10^9 + 7)$ 的余数。

约束

• $2 \leq N \leq 2\times 10^5$
• $0 \leq M \leq 2\times 10^5$
• $1 \leq A_i < B_i \leq N$
• 对于所有 $i$，都有 $(A_i, B_i)$ 是不同的。
• 所有输入的值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

输出

打印结果。 如果无法从城市 $1$ 到城市 $N$，则打印 $0$。

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

2

从城市 $1$ 到城市 $4$ 所需的最短时间是 $2$ 小时，有两条路径可以达到：$1 \to 2 \to 4$ 和 $1 \to 3 \to 4$。

4 3
1 3
2 3
2 4

1

从城市 $1$ 到城市 $4$ 所需的最短时间是 $3$ 小时，有一条路径可以达到：$1 \to 3 \to 2 \to 4$。

2 0

0

无法从城市 $1$ 到城市 $2$，这时应该输出 $0$。

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

4