Gerald 与巨型国际象棋

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

在 $h\times w$ 的棋盘上，一个兵从左上角出发，每步只能向下或向右移动一格，且不能进入黑格。给定 $n$ 个黑格，求到达右下角的路径数，对 $10^9+7$ 取模。

输入格式

第一行包含 $h,w,n$。接下来 $n$ 行每行包含一个黑格的行、列坐标。保证黑格互不相同，且起点、终点不是黑格。

输出格式

输出一个整数，表示合法路径数。

样例输入 1

3 4 2
2 2
2 3

样例输出 1

2

样例输入 2

100 100 3
15 16
16 15
99 88

样例输出 2

545732279

数据范围

$1\le h,w\le10^5$，$1\le n\le2000$；黑格互不相同，起点和终点为白格。