0228 - 人権 (Human Rights)

時間制限 8 秒 / メモリ制限 256 MB / 得点 5 / Writer root / x 9 / 統計 /


TLE
8sec
MLE
256MB
得点
5

問題

ミズゴロウのゴロウくんは, 第 12 回日本積分オリンピック(Japanese Olympiad in Integration)の予選を受験しようと思っている. しかし, JOIの受験資格は, 高校 2 年生相当の学年以下の人間にあるため, 人権がないゴロウくんには受験資格がない. しかし, 国際積分オリンピック日本委員会では, 第 12 回JOI予選の成績が最も優秀なミズゴロウに人権を与え, 第 12 回JOI本選に特別に招待することにした.

ゴロウくんを含め, N 匹のミズゴロウがJOI予選を受けようと考えている. 試験会場には M 個の席が一直線上にあり, 不正が起きないようにそれぞれのミズゴロウは1つ以上の席を開けて座らなければならない. しかし, M 個のうち K 個の席は壊れている.

入力として N, M, K の値と K 個の壊れている席の情報が与えられたとき, ミズゴロウたちが席にかける方法の総数を 100000 で割ったあまりを求めるプログラムを作成せよ. ただし, それぞれのミズゴロウは区別しない.

入力

入力は K + 1 行からなる.
1 行目には 3 つの整数 N, M, K ( 1 ≦ N ≦ 3000, 1 ≦ M ≦ 3000, 0 ≦ K ≦ M ) が空白を区切りとして書かれている.
1 + i 行目 ( 1 ≦ i ≦ K ) には, 1 つの整数 Ai ( 1 ≦ Ai ≦ M ) が与えられる. これは, 壊れている席が左から数えて何番目の席かを表す. Ai はすべて異なる.

出力

ミズゴロウたちが条件を満たし席に座る方法の総数を 100000 で割ったあまりを1行で出力せよ.

入出力例

入力例 1

2 3 1
1

出力例 1

0

入力例 1 では, 席 2 と 3 が使えるが, 2 匹のミズゴロウが残っているため, 席を 1 つ以上開けて座ることが出来ない. したがって座る方法は 0 通りである.

入力例 2

2 3 1
2

出力例 2

1

入力例 2 では, 席 1 と 3 が使え, 2 匹のミズゴロウが開いた席に座れば問題の条件を満たす. それ以外に問題の条件を満たす座り方はないため, 座り方の総数は 1 通りである.

入力例 3

1 3000 0

出力例 3

3000

入力例 3 では, ゴロウくん以外にJOI予選を受けるミズゴロウがいない. したがって, 条件を満たす座り方は, ゴロウくんが座れる席の組み合わせの数と等しく 3000 通りになる.

入力例 4

10 35 4
3
6
7
35

出力例 4

17150

入力例 4 では, 条件を満たす席の座り方が 917150 通りある. したがって, それを 100000 で割った余りである 17150 を出力する.