C - 正直者の高橋くん Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたと高橋君は、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

この入力例に対する図は以下の通りです。