题目链接：http://codeforces.com/contest/560/problem/E
给你一个n*m的网格，有k个坏点，问你从(1,1)到(n,m)不经过坏点有多少条路径。
先把这些坏点排序一下。
dp[i]表示从(1,1)到第i个坏点且不经过其他坏点的路径数目。
dp[i] = Lucas(x[i], y[i]) - sum(dp[j]*Lucas(x[i]-x[j], y[i]-x[j])) , x[j] <= x[i] && y[j] <= y[i] //到i点所有的路径数目 - 经过其他点的路径数目
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef __int64 LL;
typedef pair <int, int> P;
const int N = 2e3 + ;
struct Node {
LL x, y;
bool operator <(const Node &cmp) const {
return x == cmp.x ? y < cmp.y : x < cmp.x;
}
}node[N];
LL mod = 1e9 + ;
LL dp[N]; //经过i点不经过其他点的case数
LL f[]; //阶乘 LL Pow(LL a , LL n , LL mod) {
LL res = ;
while(n) {
if(n & )
res = res * a % mod;
a = a * a % mod;
n >>= ;
}
return res;
} LL Comb(LL a , LL b , LL mod) {
if(a < b) {
return ;
}
if(a == b) {
return ;
}
return f[a] * Pow(f[a - b] * f[b] % mod, mod - , mod) % mod;
} LL Lucas(LL n , LL m , LL mod) {
LL ans = ;
while(m && n && ans) {
ans = (ans * Comb(n % mod , m % mod , mod)) % mod;
n /= mod;
m /= mod;
}
return ans;
} int main()
{
f[] = ;
for(LL i = ; i <= ; ++i) {
f[i] = f[i - ] * i % mod;
}
LL row, col, sum;
int n;
scanf("%lld %lld %d", &row, &col, &n);
for(int i = ; i <= n; ++i) {
scanf("%lld %lld", &node[i].x, &node[i].y);
node[i].x--, node[i].y--;
}
sort(node + , node + n + );
for(int i = ; i <= n; ++i) {
sum = ;
for(int j = ; j < i; ++j) {
if(node[i].x >= node[j].x && node[i].y >= node[j].y) {
sum = (dp[j]*Lucas(node[i].x + node[i].y - node[j].x - node[j].y, node[i].x - node[j].x, mod) % mod + sum) % mod;
}
}
dp[i] = ((Lucas(node[i].x + node[i].y, node[i].x, mod) - sum) % mod + mod) % mod;
}
sum = ;
for(int i = ; i <= n; ++i) {
sum = (dp[i]*Lucas(row + col - - node[i].x - node[i].y, row - - node[i].x, mod) % mod + sum) % mod;
}
printf("%lld\n", ((Lucas(row + col - , col - , mod) - sum) % mod + mod) % mod);
return ;
}