← 返回题目列表

Codeforces · 559/C

C. 杰拉德和巨型国际象棋

中文机器翻译题面 查看原题

巨型国际象棋在杰拉尔迪恩很常见。我们不会深入研究游戏规则,我们只是说游戏在 h × w 的场地上进行,并且它被涂成两种颜色,但与国际象棋不同。场中几乎所有单元格都是白色的,只有一些单元格是黑色的。目前,杰拉德正在与他的朋友波拉德完成一场巨型国际象棋比赛。杰拉德几乎就赢了,而他唯一需要获胜的就是将棋子从棋盘左上角(它现在所在的位置)移到右下角。杰拉德对胜利充满信心,他产生了兴趣,他能通过多少种方式获胜?

杰拉德留下的棋子可以有两种走法:向下一格或向右一格。另外,也不能去黑格,否则杰拉德还是输了。场上已经没有其他棋子或棋子了,因此,根据巨型国际象棋的规则,杰拉德移动他的棋子,直到游戏结束,而波拉德只是看着这个过程。

输入

输入的第一行包含三个整数:h、w、n - 棋盘的边数和黑色单元格的数量 (1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000)。

接下来的 n 行包含黑色单元的描述。这些行的第 i 行包含数字 ri, ci (1 ≤ ri ≤ h, 1 ≤ ci ≤ w) — 第 i 个单元格的行号和列号。

保证左上和右下单元格为白色,并且描述中的所有单元格是不同的。

输出

打印一行 — 将 Gerald 的棋子从左上角移动到右下角的方法数模 109 + 7 的余数。

示例

输入 #1

3 4 2
2 2
2 3

输出 #1

2

输入 #2

100 100 3
15 16
16 15
99 88

输出 #2

545732279