You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在你所在的城市有 $n$ 个月饼店, 你要从$1$ 号月饼店走到 $n$ 号月饼店送货.

题目描述

有 $n$ 个月饼店和 $m$ 条双向道路, 第 $i$ 条道路连接了 $u_i, v_i$ 两家月饼店, 你想知道从 $1$ 号点到 $n$ 号点一共有多少种不同的最短路径?

注意: 答案可能很大, 需要对 $1000000007$ 求模.

输入格式

第一行两个整数 $n, m$ 表示有 $n$ 个月饼店和 $m$ 条道路

接下来 $m$ 行, 每行两个整数 $u_i, v_i$ 表示从 $u_i$ 到 $v_i$ 有一条无向边

输出格式

输出一个整数表示从 $1$ 号店到 $n$ 号店有多少种不同的最短路径.

样例 #1

样例输入 #1

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

样例输出 #1

2

样例 #2

样例输入 #2

4 3
2 3
2 4
1 3

样例输出 #2

1

样例 #3

样例输入 #3

2 0

样例输出 #3

0

样例 #4

样例输入 #4

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

样例输出 #4

4

提示

• $2\ \leq\ n\ \leq\ 2\times\ 10^5$
• $0\ \leq\ m\ \leq\ 2\times\ 10^5$
• $1\ \leq\ u_i, v_i\ \leq\ n$