← 返回题单
题单练习 动态规划的优化
← 上一题 下一题 →

A7065 | Welcome24ever 和象棋

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

在 Geraldion，有一种“巨型国际象棋”。Welcome24ever 只剩下一个兵需要从棋盘左上角走到右下角就能获胜。

棋盘大小为 $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)$ 都是白色，且所有黑格互不相同。

输出格式

输出一行一个整数，表示答案对 $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
C++ 编辑器
输入
输出