J21 习题-5 巨型国际象棋

题目描述

巨型象棋在杰拉尔丁很常见。我们不会深究游戏规则，我们只会说游戏是在 $h\times w$ 棋盘内进行，它被画成两种颜色，但不像国际象棋。几乎所有的方格都是白色的，只有一些方格是黑色的。目前，杰拉尔德正在与他的朋友波拉德完成一场巨型国际象棋比赛。杰拉尔德几乎赢了，他唯一需要赢的就是把棋子从棋盘的左上角（现在的位置）带到右下角。杰拉尔德对胜利如此自信，他在多少种方式下能获得胜利？

杰拉尔德留下的棋子有两种方式：一个向下，一个向右。此外，它不能去黑色方格，否则杰拉尔德还是输了。赛场上没有其他棋子或棋子，因此，根据巨型国际象棋的规则，杰拉尔德移动他的棋子，直到比赛结束，而波拉德只是在观察这个过程。

输入格式

输入的第一行包含三个整数：$h$， $w$， $n$ ， 表示棋盘的高和宽，以及黑色方格的数量。

接下来的 $n$ 行包含黑单元格的描述。这些行中的第 $i$ 行包含数字 $r_i$， $c_i$（ $1\le r_i \le h$,  $1 \le c_i \le w$），表示第 $i$个单元格的行和列的编号。

可以保证左上和右下的方格是白色的，并且描述中的所有方格都是不同的。

输出格式

输出一行，将杰拉尔德的棋子从左上角移动到右下角的方法数量，模$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

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le h$, $w \le 10^5$, $1 \le n\le 2000$。