Portal: https://codeforces.com/contest/560/problem/E

meaning of the title

to one individual n ∗ m of Chess disc ， Think want from ( 1 , 1 ) go reach ( n , m ) ， but yes also k individual bad spot no can through too ， ask have many less species square case ？ Give an n*m chessboard, want to go from (1,1) to (n,m), but k bad points can't pass through. How many schemes are there? Give an n * m chessboard, want to go from (1,1) to (n,m), but k bad points can't pass through. How many schemes are there?

thinking

because by n and m all have 1 e 5 ， place with no can f [ i ] [ j ] ， but yes k only have 2000 ， place with I Men Test Worry about bad spot O ( n 2 ) do method . Because both N and m have 1e5, we can't f[i][j], but k is only 2000, so we consider the bad point O(n^2) approach. Because both n and m have 1e5, we can't f[i][j], but k is only 2000, so we consider the bad point O(n2) approach.

false as I Men Pieces lift reach reach bad spot of square case ， also can with take ( n , m ) this one spot see Out The first k + 1 individual bad spot ， place with Test Worry about each two individual bad spot of between square case . If we enumerate the schemes that reach the bad point, we can also see the k+1 bad point from (n,m), so consider the scheme between each two bad points. If we enumerate the schemes that reach the bad point, we can also see the k+1 bad point from (n,m), so consider the scheme between each two bad points.

can with PUSH Out ( x 1 , y 1 ) go reach ( x 2 , y 2 ) of square case by C x 2 − x 1 + y 2 − y 1 x 2 − x 1 . The scheme that can push (x1,y1) to (x2,y2) is C_{x_2-x_1+y_2-y_1}^{x_2-x_1}. The scheme from (x1,y1) to (x2,y2) is Cx2 − X1 + y2 − y1 − x2 − x1.

place with from ( 1 , 1 ) Out hair reach reach of bad spot have C x + y − 2 x − 1 . So the bad point of departure from (1,1) is C_{x+y-2}^{x-1}. Therefore, the bad points from (1,1) are Cx+y − 2x − 1.

set up two individual bad spot by i and j ， and And no can through too j reach reach i ， place with want hold reach reach i of square case reduce fall j reach i of square case ， Namely Let the two bad points be i and j, and you can't reach i through J, so subtract the scheme from J to i, that is Let the two bad points be i and j, and you can't reach i through J, so subtract the scheme from J to i, that is

d p [ i ] = d p [ i ] − d p [ j ] ∗ ∑ j = 1 i − 1 C p [ i ] . x − p [ j ] . x + p [ i ] . y − [ j ] . y p [ i ] . x − p [ j ] . x dp[i]=dp[i]-dp[j]*\sum_{j=1}^{i-1}C_{p[i].x-p[j].x+p[i].y-[j].y}^{p[i].x-p[j].x} dp[i]=dp[i]−dp[j]∗j=1∑i−1​Cp[i].x−p[j].x+p[i].y−[j].yp[i].x−p[j].x​

this kind one straight Pieces lift lower go ， a n s = d p [ k + 1 ] ， Namely reach reach most after one individual bad spot ( n , m ) of square case number . Keep enumerating, ans=dp[k+1], that is, the number of schemes that reach the last bad point (n,m). Keep enumerating, ans=dp[k+1], that is, the number of schemes that reach the last bad point (n,m).

Code

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

typedef long long ll;
typedef pair<ll, ll> pll;

 const ll mod = 1e9 + 7;


const int N = 2e5 + 10;

ll F[N], inv[N], invF[N];

void init() {
    F[0] = inv[0] = invF[0] = F[1] = inv[1] = invF[1] = 1;
    for(int i = 2;i < N; i++) {
        F[i] = F[i - 1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        invF[i] = invF[i - 1] * inv[i] % mod;
    }
}

ll C(int m, int n) {
    if(m < 0 || n < 0 || m < n) return 0;
    ll ans = F[m];
    ans = ans * invF[n] % mod;
    ans = ans * invF[m - n] % mod;
    return ans;
}

bool cmp(pll a, pll b) {
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

void solve()  {
    init();
    int n, m, k; cin >> n >> m >> k;
    vector<ll> dp(k + 10);
    vector<pll> p(k + 10);
    for(int i = 1;i <= k; i++) cin >> p[i].first >> p[i].second;
    sort(p.begin() + 1, p.begin() + k + 1, cmp);
    p[++k].first = n; p[k].second = m;
    for(int i = 1;i <= k; i++) {
        dp[i] = C(p[i].first + p[i].second - 2, p[i].first - 1);
        for(int j = 1;j < i; j++) { // j to i
            if(p[i].first >= p[j].first && p[i].second >= p[j].second) {
                // int temp = C(p[i].first - p[j].first + p[i].second - p[j].second, p[i].first - p[j].first);
                dp[i] = (dp[i] - dp[j] * C(p[i].first - p[j].first + p[i].second - p[j].second, p[i].first - p[j].first) % mod) % mod;
            }
        }
    }
    cout << (dp[k] % mod + mod) % mod << endl;
}

signed main() {
    solve();
}