AT_dp_y Grid 2

题目描述

有一个高为 $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$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$ $N$ $r_1$ $c_1$ $r_2$ $c_2$ $\ldots$ $r_N$ $c_N$

输出格式

输出从 $(1, 1)$ 到 $(H, W)$ 的路径数，对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

3 4 2
2 2
1 4

输出 #1

3

输入输出样例 #2

输入 #2

5 2 2
2 1
4 2

输出 #2

0

输入输出样例 #3

输入 #3

5 5 4
3 1
3 5
1 3
5 3

输出 #3

24

输入输出样例 #4

输入 #4

100000 100000 1
50000 50000

输出 #4

123445622

说明/提示

限制条件

• 所有输入均为整数。
• $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)$ 都是空格子。

样例解释 1

路径共有如下图的 $3$ 种。

样例解释 2

也有可能不存在任何路径。

样例解释 4

不要忘记输出答案时要对 $10^9 + 7$ 取模。

由 ChatGPT 4.1 翻译