51Nod 1486 大大走格子

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

typedef long long LL;
const int maxn=2000+100;
const int maxm=100000+100;
const int mod=1e9+7;

LL fac[maxm*2],inv[maxm];
struct Node{
  
  int x,y;
}node[maxn];
LL dp[maxn][2];

inline bool cmp(Node a,Node b){
  
  return a.x==b.x?a.y<b.y:a.x<b.x;
}

LL mypow(LL a,LL b){
  
  LL sum=1;
  while(b){
    
    if(b&1) sum=sum*a%mod;
    a=a*a%mod;
    b>>=1;
  }
  return sum;
}

void init(){
  
  fac[0]=1;
  for(int i=1;i<maxm*2;i++) fac[i]=fac[i-1]*i%mod;
  inv[maxm-1]=mypow(fac[maxm-1],mod-2);
  for(int i=maxm-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}

inline LL C(int n,int m){
  
  if(n<m) return 0;
  return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main(){
  
  init();
  int n,m,num;
  scanf("%d%d%d",&n,&m,&num);
  for(int i=1;i<=num;i++) scanf("%d%d",&node[i].x,&node[i].y);
  node[++num].x=1,node[num].y=1;
  node[++num].x=n,node[num].y=m;
  sort(node+1,node+1+num,cmp);
  dp[1][1]=1;
  for(int i=1;i<=num;i++){
    
    for(int j=1;j<i;j++){
      
      if(node[j].y>node[i].y) continue;
      int xci=node[i].x+node[i].y-node[j].x-node[j].y;
      int yci=node[i].x-node[j].x;
      dp[i][0]=(dp[i][0]+dp[j][1]*C(xci,yci)%mod)%mod;
      dp[i][1]=(dp[i][1]+dp[j][0]*C(xci,yci)%mod)%mod;
    }
  }
  LL key=((dp[num][0]-dp[num][1])%mod+mod)%mod;
  printf("%lld\n",key);
}