最短路径条数

题目描述

AtCoder 共和国有 $N$ 个城市,编号为 $1$ 到 $N$,以及 $M$ 条道路,编号为 $1$ 到 $M$。

使用道路 $i$,可以在 1 小时内从城市 $A_i$ 到达城市 $B_i$,也可以反向通行。

求从城市 $1$ 到达城市 $N$ 的最早时间方案共有多少条路径。

由于答案可能很大,请对 $(10^9 + 7)$ 取模后输出。

输入格式

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

$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

数据范围

• $2 \le N \le 2\times 10^5$
• $0 \le M \le 2\times 10^5$
• $1 \le A_i \lt B_i \le N$
• 数对 $(A_i, B_i)$ 各不相同
• 输入均为整数