AT_abc211_d [ABC211D] Number of Shortest paths

[problemUrl]: https://atcoder.jp/contests/abc211/tasks/abc211_d 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 $ と出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ A_i\