006 - JOI 中学校のクラス事情 (Classroom Trouble in JOI Junior High School)

問題

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

A 組の N 人の生徒は, 皆とても人見知りで, 友達が両隣にいないとどうしても落ち着かない. A 組の中に友達同士である 2 人組は M 組存在している. 出席番号が i (1 ≤ i ≤ N) の生徒を生徒 i と呼ぶことにすると, j (1 ≤ j ≤ M) 番目の友達の組は生徒 U_j と生徒 V_j からなる. また, 厄介なことに, 生徒たちは自分と出席番号が遠い人とは話したがらず, 友達関係を築かない. 具体的には, 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) 行目には, 整数 U_i と V_i (1 ≤ U_i < V_i ≤ N)が空白区切りで書かれている. これは, 生徒 U_i と生徒 V_i が友達であることを表す. ここで, |U_i - V_i| ≤ d であることが保証されている. また, i ≠ j ならば U_i ≠ U_j または V_i ≠ V_j が保証される.

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

出力

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

入出力例

入力例 1

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

出力例 1

4

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

入力例 2

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

出力例 2

120

入力例 3

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

出力例 3

7776