Phân tích:

Số cách để đi từ ô ~(i,j)~ đến ô ~(x,y)~ là ~\begin{pmatrix}x-i\\ x-i+y-j\end{pmatrix}~ có thể tính trong ~\mathcal O(1)~ nếu tính toán trước.

Giả sử ta có thể đi được đến các ô có chướng ngại vật. Gọi ~\texttt{dp}[i]~ là số cách đi từ ô ~(1,1)~ đến chướng ngại vật thứ ~i~ mà không đi qua bất cứ chướng ngại vật nào khác ngoài chướng ngại vật thứ ~i~.

Để ý rằng nếu không có chướng ngại vật nào giữa ô ~(1,1)~ và ô ~(r_i,c_i)~ thì có tất cả ~\begin{pmatrix}r_i - 1 + c_i - 1\\ r_i - 1\end{pmatrix} ~ cách để đi từ ô ~(1,1)~ đến ô ~(r_i, c_i)~. Ta có thể tính được ~dp[i]~ bằng cách trừ giá trị này cho số cách đi qua các ô vuông giữa đường đi từ ô ~(1,1)~ đến chướng ngại vật ~(r_i,c_i)~ bằng cách duyệt qua tất cả các ô ~j~ sao cho ~r_j \le r_i~ và ~c_j \le c_i~. Hay ta có:

Để có được đáp án, ta chỉ cần thêm một chướng ngại vật tại ~(H, W)~ và lấy kết quả từ mảng ~{dp}~.

Tham khảo thêm: Các kiến thức cơ bản về Tổ hợp và Nghịch đảo modulo .

Độ phức tạp: ~\mathcal O(H + W + N \log(N) + N^2)~

Code mẫu:

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

#define Hmax 100000
#define N    3000
#define MOD  1000000007

int n, m, k, dp[N + 1];
long long fac[Hmax << 1], ifac[Hmax << 1];
struct P {
    int x, y;
    bool operator<(const P& other) const {
        if (x == other.x) return y < other.y;
        return x < other.x;
    }
} point[N + 1];

int power(long long x, int p) {
    long long res = 1;
    while (p > 0) {
        if (p & 1) res = res * x % MOD;
        x = x * x % MOD, p >>= 1;
    }
    return res;
}

void genFac(int size) {
    fac[0] = 1;
    for (int i = 1; i <= size; ++i)
        fac[i] = fac[i - 1] * i % MOD;
    ifac[size] = power(fac[size], MOD - 2);
    for (int i = size; i >= 1; --i)
        ifac[i - 1] = ifac[i] * i % MOD;
}
int choose(int n, int k) {
    assert(n >= k);
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
int path(int i, int j, int x, int y) {
    assert(i <= x && j <= y);
    return choose(x - i + y - j, x - i);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    genFac(n + m - 1);
    for (int i = 0; i < k; ++i)
        scanf("%d%d", &point[i].x, &point[i].y);
    point[k] = {n, m};
    sort(point, point + k + 1);
    for (int i = 0; i <= k; ++i) {
        long long sum = path(1, 1, point[i].x, point[i].y);
        for (int j = 0; j < i; ++j)
            if (point[i].y - point[j].y >= 0) {
                sum = sum - (long long) dp[j] * path(point[j].x, point[j].y, point[i].x, point[i].y) % MOD;
                if (sum < 0) sum += MOD;
            }
        dp[i] = sum;
    }
    printf("%d\n", dp[k]);
}