Ⅳ章
あなたは"ギルド"で働いている。ある雨の降る青空の日に神仁(かみひと)と名乗る少年と出会い、夫がいるにも関わらず神仁に笑顔を向けられ惚れてしまった。 今日も神仁にどうアピールしようか悩んでいるあなたの耳に神仁の口笛を吹く音が聞こえてきた。その音を聞いた時点で理性のほとんどを破壊されたあなたは神仁のもとに向かった。神仁のいる場所は東南方向だが、方向音痴なあなたは東か南にしか進めない。残されたごく一部の理性で家族に見つかるとまずいと思ったあなたは家族を避けて行くことにした。 その上で神仁のもとに行ける経路の個数 m を 10007 で割った余りを出力せよ。
入力
1行目には空白を区切りとして南北方向の道路の本数 a，東西方向の道路の本数 bが与えられる。
2行目には, 家族の人数を表す整数 n が与えられる。
続く n 行 (3行目から n+2 行目) には、家族の位置が書かれている。 i+2 行目には空白で区切られた整数 xi, yi が書かれており、交差点 (xi, yi) に家族がいることを表す。
出力
神仁のもとに行ける経路の個数 m を 10007 で割った余りのみからなる1行である。
制約
1 ≤ a, b ≤ 1000
1 ≤ n ≤ 100
1 < xi < a
1 < yi < b
入出力例
入力例1
5 4 3 2 2 2 3 4 2
出力例1
7
入力例2
20 20 0
出力例2
9429
入力例3
1000 1000 3 10 10 20 20 30 30
出力例
3772