Description:


有一个 \(h\)\(w\) 列的棋盘,里面有一些格子是不能走的,每次可以向右或向下移动一步,现在要求从左上角走到右下角的方案数。

Input:


单组测试数据。
第一行有三个整数 \(h,w,n\) ( \(1\le h, w\le 10^5, 1\le n\le 2000\) ),表示棋盘的行和列,还有不能走的格子的数目。
接下来 \(n\) 行描述格子,第i行有两个整数 \(r_i\) , \(c_i\) ( \(1\le r_i\le h, 1\le c_i\le w\) ),表示格子所在的行和列。
输入保证起点和终点不会有不能走的格子。

Output:


输出答案对 \(1000000007\) 取余的结果。

Sample Input:


Sample Output:


题解:


嗯这题想了好久都没有头绪。。。

首先把所有点按照 \(x\) 排序,设 \(dp_i\) 表示从 \((1, 1)\) 走到点 \(i\) ,且不经过 \(1, 2, \ldots, i-1\) 号点的方案数。

你会发现任意一条经过 \(1, 2, \ldots, i-1\) 中一点的路径都有第一个经过的点。

所以就有状态转移方程:

\[ dp_i = \binom{x_i+y_i-2}{x_i-1} - \sum_{j < i, y_j \le y_i} dp_j \times \binom{x_i-x_j+y_i-y_j}{x_i-x_j}\]

我们把点 \((w, h)\) 作为最后一个点,然后答案就是 \(dp_n\)