题目描述

ZJC国度拥有编号为 $1$ 至 $N$ 的 $N$ 座城市和编号为 $1$ 至 $M$ 的 $M$ 条道路。

使用道路 $i$ ，您可以在一小时内从城市 $A_i$ 前往 $B_i$ ，反之亦然。

有多少条路可以让你尽早从城市 $1$ 到达城市 $N$ ？ 由于数目可能很大，请打印出它的模数 $(10^9 + 7)$ 。

换句话说：请求出城市$1$到城市$N$的最短路的数量并对$(10^9 + 7)$ 取模输出

输入格式

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$
数据范围如下：
$2 \leq N \leq 2\times 10^5$
$0 \leq M \leq 2\times 10^5$
$1 \leq A_{i}<B_{i} \leq N$
$(A_i, B_i)$ 成对是不同的 输入的所有值都是整数

输出格式

打印答案。如果不可能从城市 $1$ 到达城市 $N$ ，则打印 $0$ 。

样例

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

4

如图所示，从$1$到$7$有四条不同的最短路径