题目描述

给定一个 $H$ 行 $W$ 列的棋盘，棋盘上只有 $N$ 个格子是黑色的，其余格子均为白色。

在棋盘左上角 $(1,1)$ 处有一个卒，每一步可以向右或向下移动一格，但不能移动到黑色格子中。

求从左上角 $(1,1)$ 移动到右下角 $(H,W)$ 共有多少种不同的路线。

输入格式

第一行包含三个整数 $H, W, N$。
接下来 $N$ 行，每行包含两个整数 $x, y$，表示一个黑色格子的行号和列号。

输出格式

输出一个整数，表示不同路线数对 $10^9 + 7$ 取模后的结果。

数据范围

• $1 \le H, W \le 10^5$
• $1 \le N \le 2000$

保证左上角 $(1,1)$ 和右下角 $(H,W)$ 的格子是白色的。

输入样例 1

3 4 2 
2 2 
2 3

输出样例 1

2

输入样例 2

100 100 3
15 16
16 15
99 88

输出样例 2

545732279

样例解释

样例 1

棋盘为 $3$ 行 $4$ 列，黑格子位置为 $(2,2)$ 和 $(2,3)$。

从 $(1,1)$ 到 $(3,4)$ 只能向右或向下走，且不能经过黑色格子。

我们可以在棋盘上画出可走路径：

(1,1) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4)   ✅ 可行
(1,1) → (1,2) → (1,3) → (2,3) ✗ 不可行（黑格）
(1,1) → (1,2) → (2,2) ✗ 不可行（黑格）

另一个可行路径：

(1,1) → (2,1) → (3,1) → (3,2) → (3,3) → (3,4)   ✅ 可行

检查是否有其他路径：

• 如果走 $(1,1)→(2,1)→(2,2)$ 不可行（黑格）
• 如果走 $(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(3,4)$ 已算
• 如果走 $(1,1)→(1,2)→(1,3)→(2,3)$ 不可行（黑格）

因此只有 2 条可行路径。

输出为 2。

样例 2

棋盘 $100\times100$，3 个黑格子：

• $(15,16)$
• $(16,15)$
• $(99,88)$

由于黑格子较少且位置较分散，路径总数非常多，但需要排除经过这些黑格子的路径。
通过组合计数和容斥原理（或 DP 结合障碍物），可以计算出结果为 $545732279$（取模后）。

具体计算过程较为复杂，但题目保证答案在模 $10^9+7$ 意义下正确。