题目大意
有一个wxh的网格，上面有n个黑点，问你从(1,1)走到(w,h)不经过任何黑点的方案数
思路
考虑容斥
先把所有黑点按照x值进行排序方便计算
\(dp_{i}\)表示从起点走到第i个黑点不经过任何的黑点的方案数
然后\(dp_{i}=C(x_i+y_i-2,x_i-1)-\sum_{j|x_j\leq x_i,y_j\leq y_i}dp_{j}\times C(j->i)\)
这样容斥为什么是正确的，\(dp_{j}\)考虑了所有经过j的情况，其他的包含j的点都不会考虑j的贡献
所以容斥是正确的
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = 1;x = 0;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = 0, c = getchar();
while (isdigit(c)) {
x = (x<<1) + (x<<3) + c -'0';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) Write(x / 10);
putchar(x % 10 + '0');
}
//----------------------------------------------
const int N = 2e5 + 10;
const int Mod = 1e9 + 7;
int fac[N], inv[N];
int w, h, n, dp[N];
//dp表示不经过任何黑点走到第i个黑点的方案数
struct Point {
int x, y;
} p[N];
bool cmp(Point a, Point b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int add(int a, int b) {
return (a += b) >= Mod ? a - Mod : a;
}
int sub(int a, int b) {
return (a -= b) < 0 ? a + Mod : a;
}
int mul(int a, int b) {
return 1ll * a * b % Mod;
}
int fast_pow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int C(int a, int b) {
return mul(fac[a], mul(inv[b], inv[a - b]));
}
void init(int len) {
fac[0] = inv[0] = 1;
fu(i, 1, len) fac[i] = mul(fac[i - 1], i);
fu(i, 1, len) inv[i] = fast_pow(fac[i], Mod - 2);
}
int main() {
Read(h), Read(w), Read(n);
init(h + w);
fu(i, 1, n) Read(p[i].x), Read(p[i].y);
sort(p + 1, p + n + 1, cmp);
fu(i, 1, n) {
dp[i] = C(p[i].x + p[i].y - 2, p[i].x - 1);
fu(j, 1, i - 1)
if (p[j].y <= p[i].y)
dp[i] = sub(dp[i], mul(dp[j], C(p[i].x - p[j].x + p[i].y - p[j].y, p[i].x - p[j].x)));
}
int ans = C(h + w - 2, h - 1);
fu(i, 1, n) ans = sub(ans, mul(dp[i], C(h - p[i].x + w - p[i].y, h - p[i].x)));
Write(ans);
return 0;
}