Code: Gerald and Giant Chess

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
using namespace std;

const int mmod = 1000000007;

int inv_mod(int a, int b) {
    if (a == 1)
        return b;
    int div = mmod / a + 1;
    return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod);
}

int fac[222222], fac_inv[222222];

int combi(int a, int b) {
    if (a < 0 || b < 0)
        return 0;
    return (((1LL * fac[a + b] * fac_inv[a]) % mmod) * fac_inv[b]) % mmod;
}

int main() {
    fac[0] = fac_inv[0] = 1;
    for (int i = 1; i < 222222; i++) {
        fac[i] = (1LL * fac[i - 1] * i) % mmod;
        fac_inv[i] = inv_mod(fac[i], 1);
    }

    int h, w, n;
    cin >> h >> w >> n;
    vector<pair<int, int>> rc(n);
    for (int i = 0; i < n; i++)
        cin >> rc[i].first >> rc[i].second;
    sort(rc.begin(), rc.end());

    rc.push_back(pair<int, int>(h, w));

    vector<int> cnt(n + 1);
    for (int i = 0; i <= n; i++) {
        cnt[i] = combi(rc[i].first - 1, rc[i].second - 1);
        for (int j = 0; j < i; j++) {
            cnt[i] = (cnt[i] - 1LL * cnt[j] *
                                   combi(rc[i].first - rc[j].first,
                                         rc[i].second - rc[j].second)) %
                     mmod;
            cnt[i] = (cnt[i] + mmod) % mmod;
        }
    }
    cout << cnt[n] << endl;
}