AT_abc021_c.[ABC021C] 正直者の高橋くん

你和高桥君住在 AtCoder 王国。AtCoder 王国有 $N$ 个城镇，以及 $M$ 条连接城镇之间的道路，这些道路都是双向通行的。$N$ 个城镇分别被称为城镇 $1$、城镇 $2$、……、城镇 $N$。$M$ 条道路分别被称为道路 $1$、道路 $2$、……、道路 $M$。

高桥君决定去你家玩。他从城镇 $a$ 出发，经过 AtCoder 王国中的若干个城镇（可以是 $0$ 个），最终到达你家所在的城镇 $b$。

高桥君声称他走的是最短路径。高桥君很诚实，绝不会说谎。

于是，你决定统计一下从城镇 $a$ 到城镇 $b$ 的最短路径有多少条。由于答案可能非常大，请输出答案对 $1,000,000,007(=10^9+7)$ 取模后的结果。

从城镇 $a$ 到城镇 $b$ 的最短路径，指的是在所有从 $a$ 到 $b$ 的路径中，经过道路的次数最少的那种路径。

输入将以下述格式从标准输入给出。

$N$ $a$ $b$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ : $x_M$ $y_M$

• 第 $1$ 行给出 AtCoder 王国中城镇的个数 $N$，满足 $2 \leq N \leq 100$。
• 第 $2$ 行给出高桥君出发的城镇和你家所在的城镇编号 $a, b$，满足 $1 \leq a, b \leq N$，$a \neq b$，以空格分隔。
• 第 $3$ 行给出 AtCoder 王国中道路的个数 $M$，满足 $1 \leq M \leq 200$。
• 接下来的 $M$ 行，每行给出一条道路连接的两个城镇的编号 $x_i, y_i$，满足 $1 \leq x_i, y_i \leq N$，$x_i \neq y_i$，以空格分隔。
• 任意两个城镇之间都可以通过若干条道路互相到达。

输出一行，从城镇 $a$ 到城镇 $b$ 的最短路径的条数，对 $1,000,000,007$ 取模后的结果。

请不要忘记输出末尾的换行符。

样例解释 1

对于这个输入样例，图如下所示，存在如下 $4$ 条最短路径：

• $1 \to 2 \to 4 \to 5 \to 7$
• $1 \to 3 \to 4 \to 5 \to 7$
• $1 \to 2 \to 4 \to 6 \to 7$
• $1 \to 3 \to 4 \to 6 \to 7$
  

样例解释 2

对于这个输入样例，图如下所示。

由 ChatGPT 4.1 翻译