题目描述

在 Geraldion，巨型国际象棋十分常见。我们不去深究游戏的规则，只需要知道游戏发生在一个 $h×w$ 的棋盘上，并且棋盘被涂成两种颜色，但不像国际象棋那样。棋盘上几乎所有格子都是白色的，只有部分格子是黑色的。现在 Gerald 正在和他的朋友 Pollard 完成巨型国际象棋比赛。Gerald 已经接近胜利，他现在只需将一个兵从棋盘左上角（当前位置）走到右下角即可获胜。Gerald 对于胜利信心十足，因而他产生了兴趣，想要知道自己有多少种方式能够获胜？

Gerald 剩下的这个兵每次可以选择两种移动方式：向下移动一格或向右移动一格。此外，他不能走到黑色格子，否则 Gerald 仍然会输。棋盘上没有其他兵或棋子，所以根据巨型国际象棋的规则，Gerald 会持续移动直到游戏结束，而 Pollard 只是旁观。

输入格式

输入的第一行包含三个整数：$h, w, n$，表示棋盘的行数、列数以及黑格的数量（$1 \leq h, w \leq 10^{5}，1 \leq n \leq 2000$）。

接下来的 $n$ 行每行描述一个黑格。第 $i$ 行包含两个整数 $r_{i}, c_{i}$（$1 \leq r_{i} \leq h, 1 \leq c_{i} \leq w$），表示第 $i$ 个黑格所在的行和列编号。

保证左上角和右下角的格子都是白色，并且所有描述的黑格都是不同的。

输出格式

输出一行，表示将 Gerald 的兵从左上角走到右下角的方案数对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

3 4 2
2 2
2 3

输出 #1

2

输入输出样例 #2

输入 #2

100 100 3
15 16
16 15
99 88

输出 #2

545732279

说明/提示

由 ChatGPT 5 翻译