J8 实践-10 佩奇的旅行3

题目描述

猪猪共和国拥有 $N$ 座城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。

使用道路 $i$，佩奇可以在一小时内从城市 $A_i$ 旅行到 $B_i$，或者从城市 $B_i$ 旅行到城市 $A_i$。

有多少条路径可以让佩奇尽早从城市 $1$ 到达城市 $N$？

由于计数可能非常大，所以将答案 $\bmod (10^9+7)$ 后输出。

输入格式

第一行包含两个整数，图的顶点数 $N$ 和边数 $M$ ；

以下 $M$ 行中的每一行包含一对整数 $A_i$ 和 $B_i$，表示顶点 $A_i$ 和 $B_i$ 之间存在一条边 。对于每对顶点，它们之间最多有一条边，没有边将顶点连接到自身。

输出格式

一行，输出可以以让佩奇尽早从城市 $1$ 到达城市 $N$ 的路径数量 $\bmod (10^9+7)$ 的结果。

样例输入1

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

样例输出1

2

样例输入2

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

样例输出2

4

样例分析

样例1中，从城市 $1$ 到城市 $4$ 所需的最短时间为 $2$ 小时，这是通过两条路径实现的：$1 \to 2 \to 4$ 和 $1 \to 3 \to 4$

数据范围

对于 $100\%$ 的数据有： $2 \le N \le 2\times 10^5$，$0 \leq M \leq \ 2 \times 10^5$，$1 \le A_i\lt B \le N$。