A7065. Welcome24ever 和象棋
编程题
提高+/省选-
知识点
题目描述
在 Geraldion，有一种“巨型国际象棋”。Welcome24ever 只剩下一个兵需要从棋盘左上角走到右下角就能获胜。
棋盘大小为 $h \times w$，其中绝大多数格子是白色，只有 $n$ 个格子是黑色（不可走）。Welcome24ever 的兵每一步只能：
- 向右走一格；
- 或向下走一格。
他不能走到黑色格子上（否则就算输）。
请你计算：从 $(1,1)$ 走到 $(h,w)$ 的不同路径数，结果对 $10^9+7$ 取模。
棋盘大小为 $h \times w$，其中绝大多数格子是白色，只有 $n$ 个格子是黑色（不可走）。Welcome24ever 的兵每一步只能：
- 向右走一格；
- 或向下走一格。
他不能走到黑色格子上（否则就算输）。
请你计算：从 $(1,1)$ 走到 $(h,w)$ 的不同路径数，结果对 $10^9+7$ 取模。
输入格式
第一行包含三个整数 $h,w,n$，满足 $1 \le h,w \le 10^5$，$1 \le n \le 2000$。
接下来 $n$ 行，每行包含两个整数 $r_i,c_i$，表示第 $i$ 个黑格的位置，满足 $1 \le r_i \le h$，$1 \le c_i \le w$。
保证 $(1,1)$ 与 $(h,w)$ 都是白色，且所有黑格互不相同。
接下来 $n$ 行，每行包含两个整数 $r_i,c_i$，表示第 $i$ 个黑格的位置，满足 $1 \le r_i \le h$，$1 \le c_i \le w$。
保证 $(1,1)$ 与 $(h,w)$ 都是白色，且所有黑格互不相同。
输出格式
输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。
输入输出样例
输入 #1
3 4 2 2 2 2 3
输出 #1
2
输入 #2
100 100 3 15 16 16 15 99 88
输出 #2
545732279
说明/提示
## 样例解释
### 样例 #1
从 $(1,1)$ 到 $(3,4)$ 一共需要走 $2$ 次向下和 $3$ 次向右。黑格在 $(2,2)$ 与 $(2,3)$，会挡住很多路线。把所有不经过黑格的路线数一数，剩下正好有 $2$ 条，所以输出为 $2$。
### 样例 #1
从 $(1,1)$ 到 $(3,4)$ 一共需要走 $2$ 次向下和 $3$ 次向右。黑格在 $(2,2)$ 与 $(2,3)$，会挡住很多路线。把所有不经过黑格的路线数一数，剩下正好有 $2$ 条，所以输出为 $2$。