0580 - School Road 2

問題

太郎君の住んでいるJOI市は，南北方向にまっすぐに伸びる a 本の道路と，東西方向にまっすぐに伸びる b 本の道路により，碁盤の目の形に区分けされている．
南北方向の a 本の道路には，西から順に 1, 2, ... , a の番号が付けられている．また，東西方向の b 本の道路には，南から順に 1, 2, ... , b の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．
太郎君は，交差点 (1, 1) の近くに住んでおり，交差点 (a, b) の近くのJOI高校に自転車で通っている．自転車は道路に沿ってのみ移動することができる．太郎君は，通学時間を短くするため，東または北にのみ向かって移動して通学している．
現在， JOI市では， n 個の交差点 (x1, y1), (x2, y2), ... , (xn, yn) で工事を行っている．太郎君は工事中の交差点をc回まで通ることができる．
太郎君が交差点 (1, 1) から交差点 (a, b) まで，c回まで工事中の交差点を通っていい時，東または北にのみ向かって移動して通学する方法は何通りあるだろうか．太郎君の通学経路の個数 m を求めるプログラムを作成せよ．

入力

入力ファイルの1行目には，空白を区切りとして3個の整数 a, b, c が書かれている．これは，南北方向の道路の本数と，東西方向の道路の本数を表す． a, b は 0 ≦ a, b ≦ 1000 をみたす．cは、工事している交差点を通っていい回数を表す. cは、0 ≦ c ≦ 10 をみたす.
2行目には, 工事中の交差点の個数を表す整数 n が書かれている． n は 0 ≦ n ≦ 1000 をみたす．
続く n 行 (3行目から n+2 行目) には，工事中の交差点の位置が書かれている． i+2 行目には空白で区切られた整数 xi, yi が書かれており，交差点 (xi, yi) が工事中であることを表す． xi, yi は 1 ≦ xi, yi ≦ 1000 をみたす．

a b c
n
x1 y1
x2 y2
.
.
.
xn yn

出力

太郎君の通学経路の個数 m だけを含む1行からなる.

入出力例

入力例1

5 4 0
3 
2 2   
2 3   
4 2

出力例1

5

入力例2

5 4 1
3 
2 2   
2 3   
4 2

出力例2

21

入力例3

20 20 2
10
2 2   
2 3   
4 2
5 3
8 6
2 7
9 10
11 1
16 16
20 1

出力例2

2867

入力例3は答えが膨大な数になるので10007で割った余りの2867を出力する。