0729 - 京都の観光

問題

Eくんは京都に住んでいる大学生です。あるとき高校来の友人から京都駅から北東の方角にある神社Bまでの道を案内してほしいと頼まれました。しかし今は２月。年度末決算に向けてあちこちで工事をしていて通れない道路がたくさんあるようです。 ルート構築がめんどさくなってしまったEくんは京都の碁盤の目状に区切られている特性に目を付け、東または北にのみ向かうルートならば目的地にたどり着けるということに気がつきました。 また、Eくんは工事現場でのバイトをしているのでC回以内ならば工事現場を特別に通らせてもらえるようにしてもらいました。 京都駅から神社Bまで西から順に1,2,...,aと、南から順に1,2,...,bとし、工事現場の場所を(i,j)と表したとき、京都駅を(1,1)、神社Bを(a,b)とし、C回以内だけ工事現場を通り、なおかつ東または北にのみ向かうルートは何通りあるのかを求めるプログラムを作成せよ

入力

入力ファイルの一行目には、空白を区切りとして３個の整数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 を満たす。 続く 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

出力

Eくんのいけるルートの個数mだけを含む１行からなる。また、Mは10007で割ったあまりを出力する。

制約

入力例を参照してください

---

入出力例

入力例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

出力例3

2867