该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

起点路数

题目描述

一座园区中有 $N$ 个路口，编号为 $1$ 到 $N$，以及 $M$ 条道路。第 $i$ 条道路连接路口 $A_i$ 和 $B_i$，可以双向通行，走过任意一条道路都需要 $1$ 分钟。

你从路口 $S$ 出发，准备到达路口 $N$。请计算用时最少的路线共有多少条，答案对 $10^9+7$ 取模。

两条路线经过的路口序列不同，就视为不同的路线。若无法到达路口 $N$，答案为 $0$。若 $S=N$，不经过任何道路就已到达，这算作一条用时为 $0$ 的路线。

输入格式

第一行包含三个整数 $N,M,S$。

接下来 $M$ 行，第 $i$ 行包含两个整数 $A_i,B_i$，表示第 $i$ 条道路的两个端点。

所有输入均为整数，并满足：

• $2\le N\le 2\times 10^5$，$0\le M\le 2\times 10^5$。
• $1\le S\le N$。
• $1\le A_i<B_i\le N$。
• 所有数对 $(A_i,B_i)$ 互不相同，即不存在连接同一对路口的多条道路。

输出格式

输出一个整数，表示从 $S$ 到 $N$ 的最短路线条数对 $10^9+7$ 取模后的结果。

输入输出样例

输入 #1

5 4 2
1 2
1 5
2 3
3 5

输出 #1

2

输入 #2

3 1 3
1 2

输出 #2

1

输入 #3

4 1 2
1 4

输出 #3

0

样例说明

样例 1 中，最短用时为 $2$ 分钟，两条路线分别为 $2\to1\to5$ 和 $2\to3\to5$。

样例 2 中，起点就是终点，唯一的最短路线不经过任何道路。

样例 3 中，路口 $2$ 没有连接任何道路，无法到达路口 $4$。