题目描述

给定一个 $H$×$W$ 的棋盘，棋盘上只有$N$个格子是黑色的，其他格子都是白色的。

在棋盘左上角有一个卒，每一步可以向右或向下移动一格，并且不能移动到黑色格子中。

求这个卒从左上角移动到右下角，一共有多少种路线。

输入格式

第一行包含三个整数 $H,W,N$。

接下来 $N$行，每行包含两个整数 $x，y$，描述一个黑色格子位于 $x$行 $y$列。

数据保证左上角和右下角的格子都是白色的。

输出格式

输出一个整数表示结果对$10^9$+7 取模后的值。

样例

3 4 2 
2 2 
2 3

2

100 100 3
15 16
16 15
99 88

545732279

数据范围

$1≤H,W≤10^5, 1≤N≤2000$

来源

• 算法竞赛进阶指南