【题目】

Code

#include<bits/stdc++.h>
using namespace std;

#define M 200010
#define N 3010
#define int long long

#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define fr(i,j,k) for(int i=j;i<=k;++i)
#define rs(i,j,k) for(int i=j;i>=k;--i)
#define endl '\n'
#define IOS ios::sync_with_stdio(0)
#define pb(i) push_back(i)
#define pf(i) push_front(i)
#define mem(a,b) memset(a,b,sizeof a)
#define fx first
#define fy second

const int mod = 1000000000 + 7;
typedef pair<int,int> Pii;

Pii b[N];

int n,h,w;
int dp[N];
int fac[M],inv[M];

int fpow(int a, int b, const int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = (res * a) % p;
		a = (a * a) % p;
		b >>= 1;
	}
	return res;
}
int C(int n, int m, int p) {
	if (m > n) return 0;
	return  (fac[n] * inv[m]) % p * inv[n - m] % p;
}
signed main() {
	IOS;
	cin >> h >> w;
	cin >> n;
	b[n + 1] = {h,w};
	fac[0] = 1;
	fr(i,1,h + w){
		fac[i] = fac[i - 1] * i;
		fac[i] %= mod;
		inv[i] = fpow(fac[i],mod - 2,mod);
		cout << inv[i] << endl;
	}
	fr(i,1,n){
		cin >> b[i].fx >> b[i].fy;
	}
	sort(b + 1,b + 1 + n + 1);
	dp[0] = 1;
	fr(i,1,n + 1){
		dp[i] = C(b[i].fx + b[i].fy - 2,b[i].fx - 1,mod);
		fr(j,1,i - 1){
			if(b[i].fy >= b[j].fy) dp[i] -= dp[j] * C(b[i].fx - b[j].fx + b[i].fy - b[j].fy,b[i].fx - b[j].fx,mod) % mod;
			dp[i]=(dp[i]%mod+mod)%mod;
		}
	}
	cout << dp[n + 1];
	return 0;
}