问题描述

有一个网格，有 $H$ 个水平行和 $W$ 个竖直列。用 $(i, j)$ 表示位于从上往下数的第 $i$ 行和从左往右数的第 $j$ 列的方块。

在网格中，有 $N$ 个墙方块 $(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)$，其余的全部是空方块。保证方块 $(1, 1)$ 和 $(H, W)$ 是空方块。

Taro 会从方块 $(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

有三条路径如下所示：

示例输入 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$ 的取模。