第 15 回 日本情報オリンピック　模擬予選 ６

2015年12月12日
kagamiz

問題

ミズゴロウのゴロウくんは JOI 中学校の先生である. ゴロウくんは, 3 年 A 組の担任である. 今日彼は, 学級企画として, A 組の N 人の生徒にフルーツバスケットをしてもらおうと考えた. ゴロウくんは N 個の椅子を円状に並べ, 生徒たちに腰掛けるように指示をした. ところが, だれも動き出さない. 皆, どこに座ると友達が横になるかを真剣に考えているのだ.

A 組の N 人の生徒は, 皆とても人見知りで, 友達が両隣にいないとどうしても落ち着かない. A 組の中に友達同士である 2 人組は M 組存在している. 出席番号が i (1 ≦ i ≦ N) の生徒を生徒 i と呼ぶことにすると, j (1 ≦ j ≦ M) 番目の友達の組は生徒 Uj と生徒 Vj からなる. また, 厄介なことに, 生徒たちは自分と出席番号が遠い人とは話したがらず, 友達関係を築かない. 具体的には, 2 人の生徒の出席番号の差の絶対値が d を超えるとき, その 2 人が友達関係にあることはない.

ゴロウくんは腕利きの先生なので, M 組の友達関係を全て把握している. そこで, N 人全員の両隣が友達になるように生徒たちの座る席を決めてあげることにした.

このとき, ゴロウくんは座席の決め方が何通りあるのか気になった. ゴロウくんのために, 座席の決め方の総数を 100000 で割ったあまりを出力するプログラムを作成せよ. ただし, 回転させて一致する座り方は同じものとみなす.

入力

入力は M + 1 行からなる.

1 行目には 3 つの整数 N, M, d ( 3 ≦ N ≦ 100, 0 ≦ M ≦ N(N - 1)/2, 1 ≦ d ≦ 7 ) が空白を区切りとして書かれている.

1 + i (1 ≦ i ≦ M) 行目には, 整数 Ui と Vi (1 ≦ Ui < Vi ≦ N)が空白区切りで書かれている. これは, 生徒 Ui と生徒 Vi が友達であることを表す. ここで, |Ui - Vi| ≦ d であることが保証されている. また, i ≠ j ならば Ui ≠ Uj または Vi ≠ Vj が保証される.

与えられる入力データにおいては, 座席の決め方が少なくとも 1 つは存在することが保証されている.

出力

1 行に, 問題文の条件を満たす座席の決め方の総数を 100000 で割ったあまりを出力せよ.

入出力例

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


























  

6 15 5
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6


















  

10 33 6
9 10
4 10
1 5
1 2
7 10
3 5
2 5
2 8
3 4
5 9
1 6
2 4
1 4
5 8
4 7
5 7
3 7
8 10
7 8
2 3
6 10
3 6
6 9
7 9
2 7
4 5
2 6
4 9
5 10
1 3
6 7
4 6
1 7
  

4
   

120
   

7776
   

入力例 1 での生徒の座席の決め方は次の図に示すように 4 通り存在する.

この問題は tokoharu_sakura さんから頂いた問題です. この場を借りてお礼申し上げます.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．