問題
ミズゴロウのゴロウくんは, 第 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 を出力する.