排列组合lucas模板

 //codeforces 559C|51nod1486 Gerald and Giant Chess(组合数学+逆元)

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 typedef pair<int,int> pii;

 const int inf = 0x3f3f3f3f;

 const int N =2e5+;

 #define clc(a,b) memset(a,b,sizeof(a))

 const double eps = 1e-;

 const int MOD = 1e9+;

 void fre() {freopen("in.txt","r",stdin);}

 void freout() {freopen("out.txt","w",stdout);}

 inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}

 struct Point{

     int x,y;

     Point(){}

     Point(int _x,int _y):x(_x),y(_y){}

     bool operator <(const Point &rhs) const{

         if(x==rhs.x) return y<rhs.y;

         return x<rhs.x;

     }

 }p[N];

 int f[N];

 int invv[N];

 int inv(int x){

   int ret=,y=MOD-;

   while(y){

     if(y&)ret=1ll*ret*x%MOD;

     y>>=;x=1ll*x*x%MOD;

   }

   return ret;

 }

 int C(int n,int m){

   if(n<m)return ;

   int ret=1ll*f[n]*invv[m]%MOD;

   ret=1ll*ret*invv[n-m]%MOD;

   return ret;

 }

 int lucas(int n,int m){

    if(m == ) return ;

    return 1ll*C(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;

 }

 void init(int n,int m){

   f[]=;

   invv[]=;

   for(int i=;i<=n+m+;++i){

     f[i]=1ll*i*f[i-]%MOD;

     invv[i]=inv(f[i]);

   }

 }

 int sum[N];

 int main(){

     int n,m,q;

     scanf("%d%d%d",&n,&m,&q);

     init(n,m);

     for(int i=;i<=q;i++){

         int x,y;

         x=read(),y=read();

         p[i]=Point(x,y);

     }

     p[++q]=Point(n,m);

     sort(p+,p++q);

     for(int i=;i<=q;i++){

         sum[i]=lucas(p[i].x-+p[i].y-,p[i].x-);

         for(int j=;j<i;j++){

             sum[i]=(sum[i]-1LL*sum[j]*lucas(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%MOD+MOD)%MOD;

         }

     }

     printf("%d\n",sum[q]);

     return ;

 }