問題文
你和高桥生活在 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≦N≦100) 被给予。
- 2 行表示高桥将出发的城镇和您家所在的城镇的号码。 2 整数 a,b(1≦a,b≦N,a≠b) 用空格分隔。
- 3 行包含一个整数,表示 AtCoder 王国中现有的道路数量。 道路信息在 M(1≦M≦200) 被给予。
- 4 在 M 行中给出。这几天之一 i(1≦i≦M) 行是一条路 i 并列 2 一镇号 x_i,y_i(1≦x_i,y_i≦N,x_i≠y_i) 用空格分隔。
- 您可以沿着几条道路从任何城镇前往任何其他城镇。 在
出力
1 线上,镇 到 a 卡拉町 我决定计算到达 b 的最短路径的数量是 1,000,000,007 后的余数。 到
不要忘记最后的换行符。
入力例1
7 1 7 8 1 2 1 3 4 2 4 3 4 5 4 6 7 5 7 6
出力例1
4
此示例输入的图如下,具有最短路径: 4 是可能的。
- 1→2→4→5→7
- 1→3→4→5→7
- 1→2→4→6→7
- 1→3→4→6→7

入力例2
7 1 7 9 1 2 1 3 4 2 4 3 4 5 4 6 7 5 7 6 4 7
出力例2
2
此示例输入的图表如下。
