3Dl0Fy - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define maxn 100005
#define FOR(i , a , b) for(int i = a ; i <= b; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REVERSE(i , a , b) for(int i = a ; i >= b; i--)

const ll MOD = 1e9 + 7;

ll ifact[2 * maxn] , fact[2 * maxn];

ll binpow(ll a , ll b , ll c){
    ll res = 1;
    while(b){
        if(b & 1){
            res *= a;
            res %= c;
        }
        a *= a;
        a %= c;
        b >>= 1;
    }

    return res;
}

ll mod_inverse(ll a , ll m){
    return binpow(a , MOD - 2 , MOD);
}

void precompute(){
    fact[0] = 1;
    FOR(i , 1 , 2 * maxn){
        fact[i] = fact[i - 1] * i;
        fact[i] %= MOD;
    }

    ifact[2 * maxn] = mod_inverse(fact[2 * maxn] , MOD);

    REVERSE(i , 2 * maxn - 1 , 0){
        ifact[i] = ifact[i + 1] * (i + 1);
        ifact[i] %= MOD;
    }
}

ll nCk(ll n , ll k){
    if(k < 0 || k > n) return 0;
    return ((fact[n] * ifact[n - k]) % MOD) * ifact[k] % MOD;
}


struct Point{
    ll x , y;
};

bool cmp(Point &a , Point &b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

Point nanh_cuti[100005];

ll dp[100005];

int main(){
    FAST;
    int n , m , k;
    cin >> n >> m >> k;
    precompute();
    FOR(i , 1 , k){
        cin >> nanh_cuti[i].x >> nanh_cuti[i].y;
    }

    k = k + 1;
    nanh_cuti[k].x = n;
    nanh_cuti[k].y = m;
    sort(nanh_cuti + 1 , nanh_cuti + k + 1 , cmp);

    FOR(i , 1 , k){
        dp[i] = nCk(nanh_cuti[i].x + nanh_cuti[i].y - 2 , nanh_cuti[i].x - 1);
        dp[i] %= MOD;
        FOR(j , 1 , i - 1){
            if(nanh_cuti[j].x <= nanh_cuti[i].x && nanh_cuti[j].y <= nanh_cuti[i].y){
                ll dx = nanh_cuti[i].x - nanh_cuti[j].x;
                ll dy = nanh_cuti[i].y - nanh_cuti[j].y;
                dp[i] = (dp[i] - dp[j] * nCk(dx + dy , dx) % MOD + MOD) % MOD;
                dp[i] %= MOD;
            }
        }
    }

    cout << dp[k];
}