問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。 上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ で表します。

グリッドのうち、$N$ 個のマス $(r_1, c_1), (r_2, c_2), \\ldots, (r_N, c_N)$ は壁のマスであり、それら以外のマスはすべて空マスです。 マス $(1, 1)$ および $(H, W)$ は空マスであることが保証されています。

太郎君は、マス $(1, 1)$ から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス $(H, W)$ まで辿り着こうとしています。

マス $(1, 1)$ から $(H, W)$ までの太郎君の経路は何通りでしょうか？ $10^9 + 7$ で割った余りを求めてください。

制約

• 入力はすべて整数である。
• $2 \\leq H, W \\leq 10^5$
• $1 \\leq N \\leq 3000$
• $1 \\leq r_i \\leq H$
• $1 \\leq c_i \\leq W$
• マス $(r_i, c_i)$ はすべて相異なる。
• マス $(1, 1)$ および $(H, W)$ は空マスである。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $N$ $r_1$ $c_1$ $r_2$ $c_2$ $:$ $r_N$ $c_N$

出力

マス $(1, 1)$ から $(H, W)$ までの太郎君の経路は何通りか？ $10^9 + 7$ で割った余りを出力せよ。

入力例 1

3 4 2
2 2
1 4

出力例 1

3

経路は次図の $3$ 通りです。

入力例 2

5 2 2
2 1
4 2

出力例 2

0

経路が存在しない場合もあります。

入力例 3

5 5 4
3 1
3 5
1 3
5 3

出力例 3

24

入力例 4

100000 100000 1
50000 50000

出力例 4

123445622

答えを $10^9 + 7$ で割った余りを出力することを忘れずに。