题目描述

某国有 $N$ 个城市，从 $1$ 到 $N$ 编号，有 $M$ 条道路，从 $1$ 到 $M$ 编号。

道路 $i$ 连接城市 $A_i$ 和 $B_i$，长度是 $1$。

从城市 $1$ 到城市 $N$ 有多少条最短路径？

由于答案可能很大，输出它除以 $10^9+7$ 的余数。

限制

$2≤N≤2×10^5$ $0≤M≤2×10^5$ $1≤A_i<B_i ≤N$ 数对 $(A_i, B_i)$ 两两不同。 输入的值都是整数。

输入格式

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

输出格式

输出答案。

4 5

2 4

1 2

2 3

1 3

3 4

样例二 

输入 
7 8

1 3

1 4

2 3

2 4

2 5

2 6

5 7

6 7

输出 
4