もんだい
hoj町は縦に $a$ 本の道と横に $b$ 本の道で構成されています。
この町に住むNASSUN君は今度、「はじめてのおかいもの」という番組に出演することになりました。
そこで、NASSUN君は自宅 $(1,1)$ から $n$ 個のお店を通って買い物をし、NASSUN君の祖父母の家 $(a,b)$ へ向かうことにしました。
しかし、尺の都合上、NASSUN君の家から祖父母の家まで最短距離で行かないと間に合いません。
ですが、NASSUN君も番組スタッフも道がよくわかりません。
全てのお店を通って祖父母の家に行くルートが何通りあるかを求めるプログラムを作ってあげましょう。
なお、一つの地点に二つ以上のお店があることはありません。
にゅうりょく
1 行目に整数 $a,b$ が与えられる。
2 行目に整数 $n$ が与えられる。
3 行目から $n+2$ 行目にはお店の位置 $x,y$ が昇順で与えられる。
しゅつりょく
全てのお店を通って祖父母の家に行くルートの数を $10007$ で割った余りを出力せよ。出力の最後に改行を入れること。
せいやく
全ての入出力ケースについて以下を満たす。
- $3 \leq a, b \leq 1000$
- $1 \leq n \leq 100$
- $2 \leq x \leq a$
- $2 \leq y \leq b$
※祖父母の家がお店になっていることはない - 必ず全ての店を通れるようになっている
にゅうしゅつりょくれい
入力例1
3 3
1
2 3
出力例1
3
入力例2
5 5
3
2 2
2 4
3 5
出力例2
4
ちなみに
この問題はei1906の「はじめてのさくもん」である。
図がなかったりするが、やさしい目で見てほしい。