分为两个阶段：

1. 填出一个最小的矩形。设这个矩形左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$，那么方案数是 $(x_2-x_1+1)(y_2-y_1+1)-n$ 的阶乘。

2. 对矩形进行扩展，每次往上下左右的一个方向扩一格。

难点在于后者。可以发现，向上与向下扩展是本质相同的，向左和向右也是。于是可以归为横向与纵向扩展两类操作，计算这个方案数后，再分配到上下左右。对于横向，分配的方案数为 $\binom{(x_1-1)+(R-x_2)}{x_1-1}$，纵向则为 $\binom{(y_1-1)+(C-y_2)}{y_1-1}$。

设 $dp_{i,j}$ 表示将当前矩形扩展到长为 $i$ 宽为 $j$ 的方案数，那么有转移：

朴素转移即可。时间复杂度 $\mathcal{O}(n+RC)$。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 9e6 + 10;
const int MAXM = 3e3 + 10;
const int mod = 1e9 + 7;

int R, C, n, fac[MAXN], dp[MAXM][MAXM], c[MAXM][MAXM];

int main() {
	scanf("%d%d%d", &R, &C, &n), *fac = 1;
	for (int i = 1; i <= 9e6; i++) fac[i] = (ll)fac[i - 1] * i % mod;
	for (int i = 0; i <= 3e3; i++) c[i][0] = 1;
	for (int i = 1; i <= 3e3; i++) {
		for (int j = 1; j <= i; j++) {
			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
			c[i][j] < mod || (c[i][j] -= mod);
		}
	}
	int lx = R, ly = C, rx = 0, ry = 0;
	for (int i = 1, x, y; i <= n; i++) {
		scanf("%d%d", &x, &y);
		lx = min(lx, x), rx = max(rx, x);
		ly = min(ly, y), ry = max(ry, y);
	}
	dp[rx - lx + 1][ry - ly + 1] = 1;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (!dp[i][j]) continue;
			dp[i + 1][j] = (dp[i + 1][j] + (ll)dp[i][j] * fac[j]) % mod;
			dp[i][j + 1] = (dp[i][j + 1] + (ll)dp[i][j] * fac[i]) % mod;
		}
	}
	int ans = (ll)fac[(rx - lx + 1) * (ry - ly + 1) - n] * dp[R][C] % mod;
	ans = (ll)ans * c[lx - 1 + R - rx][lx - 1] % mod * c[ly - 1 + C - ry][ly - 1] % mod;
	printf("%d", ans);
}