Damaged Chessboard

题目描述

给定一个 $n \times m$ 的棋盘，最开始有一个棋子位于 $(1,1)$，每次可以将棋子向右或者向下移动一步，请求出棋子移动到 $(n,m)$ 的方案数。

上述是一个典型的动态规划问题，但是这次，Orange的棋盘发生了破损，这意味着棋盘上会有一些格子无法被移动到。Orange想知道，在棋盘上有若干位置破损后，棋子从 $(1,1)$ 移动到 $(n, m)$ 的方案数是多少？

答案可能很大，请对 $10^9+7$ 取 $\bmod$。

输入格式

第一行包含3个整数 $n,m,k$，表示棋盘大小 $n \times m$ 和破损的位置数 $k$。 接下来 $k$ 行，每行两个整数 $x, y$，表示该位置发生了破损，棋子无法到达。

数据范围

$n, m \le 10^5$ $k \le 5000$ 保证损坏格子位置各不相同且起点和终点一定完好。

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

3 4 2
2 2
2 3

样例输出 #1

2