### 问题描述 在一个有 $n$ 个城市的王国中，小蓝和小桥分别生活在城市 $1$ 和城市 $n$。这些城市间有 $m$ 条双向路径，第 $i$ 条路径连接城市 $a_i$ 和城市 $b_i$，通行时间为 $1$ 小时。小蓝想要尽快到达小桥的城市，请问他有多少种可行路径。由于答案可能非常大，因此将答案对 $10^9+7$ 取模。 ### 输入格式 第一行包含两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示存在一条连接城市 $a_i$ 和城市 $b_i$ 的双向路径。 数据范围保证：$2 \leq n \leq 2 \times 10^5$，$0 \leq m\leq 2\times10^5$，$1 \leq a_i < b_i \leq n$。 ### 输出格式 输出一个整数，表示小蓝最快到达小桥的城市的方案数，答案对 $10^9+7$ 取模。 ### 输入样例 ``` 4 4 1 2 1 3 3 4 2 4 ``` ### 输出样例 ``` 2 ``` ### 样例解释 存在两条最短路径 $1 \rightarrow 2 \rightarrow 4$ 和 $1 \rightarrow 3 \rightarrow 4$，用时均为 $2$ 小时。