题目描述

AtCoder 国には $1$ から $N$ の番号がついた $N$ 個の都市と、$1$ から $M$ の番号がついた $M$ 個の道路があります。

道路 $i$ を通ると都市 $A_i$ と都市 $B_i$ の間を双方向に $1$ 時間で移動することができます。

都市 $1$ から都市 $N$ へ最も早く移動することができる経路は何通りありますか？
答えは非常に大きくなる可能性があるので $(10^9+7)$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

答えを出力せよ。
都市 $1$ から都市 $N$ へ移動することが出来ない場合は $0$ と出力せよ。

题目大意

Atcoder 国有 $N$ 座城市，从 $1$ 到 $N$ 编号，$M$ 条双向道路，第 $i$ 条道路连接 $A_i$ 和 $B_i$ 号城市。

请求出从 $1$ 号城市到 $N$ 号城市不同最短路径的数量，对 $10^9+7$ 取模。

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

2

4 3
1 3
2 3
2 4

1

2 0

0

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

4

提示

制約

• $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)$ は相異なる
• 入力に含まれる値は全て整数である

Sample Explanation 1

都市 $1$ から都市 $4$ へは最短 $2$ 時間で移動することができ、それを実現する経路は $1\ \to\ 2\ \to\ 4$ と $1\ \to\ 3\ \to\ 4$ の $2$ つです。

Sample Explanation 2

都市 $1$ から都市 $4$ へは最短 $3$ 時間で移動することができ、それを実現する経路は $1\ \to\ 3\ \to\ 2\ \to\ 4$ の $1$ つです。

Sample Explanation 3

都市 $1$ から都市 $2$ に移動することはできません。この場合 $0$ を出力してください。