Description
小C所在的城市的道路构成了一个方形网格，它的西南角为(0,0)，东北角为(N,M)。小C家住在西南角，学校在东北角。现在有T个路口进行施工，小C不能通过这些路口。小C喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小C又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小C只需要让你求出路径数mod P的值。
Input
第一行，四个整数N、M、T、P。
接下来的T行，每行两个整数，表示施工的路口的坐标。
Output
一行，一个整数，路径数mod P的值。
Sample Input
3 4 3 1019663265
3 0
1 1
2 2
3 0
1 1
2 2
Sample Output
8
HINT
1<=N,M<=10^10
0<=T<=200
p=
1000003或p=
1019663265
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DP+lucas定理+中国剩余定理~
用f[i]表示到第i个断点且没有经过其余任何断点的路径总数，那么我们把断点排序，f[i]=c(f[i].x+f[i].y,f[i].x)-sum{f[j]*C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x)}，其中j<i && a[j].x<=a[i].x && a[j].y<=a[i].y。
所以要求的就是组合数……模数为1000003时，它是个质数，所以直接用lucas定理就行了，模数为1019663265时，它不是质数，就要用中国剩余定理。
其实没必要开long long的，我只是懒得改了而已，略略略。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long longll n,m,mod,tot,f[202],pri[]={0,3,5,6793,10007};struct node{ll x,y;bool operator < (const node&u) const{return x==u.x ? y<u.y:x<u.x;}
}a[202];ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;
}ll mi(ll u,ll v)
{ll now=1;for(;v;v>>=1,u=u*u%mod) if(v&1) now=now*u%mod;return now;
}struct luca1{ll sheng[1000005],jiang[1000005];void init(){sheng[0]=jiang[0]=1;for(int i=1;i<mod;i++) sheng[i]=sheng[i-1]*i%mod;jiang[mod-1]=mi(sheng[mod-1],mod-2);for(int i=mod-2;i;i--) jiang[i]=jiang[i+1]*(i+1)%mod;}ll c(ll n,ll m){if(n<m) return 0;if(n<mod && m<mod) return sheng[n]*jiang[m]%mod*jiang[n-m]%mod;return c(n%mod,m%mod)*c(n/mod,m/mod)%mod;}
}lu1;struct luca2{ll sheng[5][1000005],jiang[5][1000005];void init(){for(int k=1;k<=4;k++){ll mod=pri[k];sheng[k][0]=jiang[k][0]=1;for(int i=1;i<mod;i++) sheng[k][i]=sheng[k][i-1]*i%mod;jiang[k][mod-1]=mi(sheng[k][mod-1],mod-2);for(int i=mod-2;i;i--) jiang[k][i]=jiang[k][i+1]*(i+1)%mod;}}ll c(ll n,ll m,ll mod,int k){if(n<m) return 0;if(n<mod && m<mod) return sheng[k][n]*jiang[k][m]%mod*jiang[k][n-m]%mod;return c(n/mod,m/mod,mod,k)*c(n%mod,m%mod,mod,k)%mod;}void gcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return;}gcd(b,a%b,y,x);y-=a/b*x;}void add(ll &a,ll b){a=a+b>=mod ? a+b-mod:a+b; }ll crt(ll n,ll m){ll tmp,x,y,ans=0;for(int k=1;k<=4;k++){tmp=mod/pri[k];gcd(tmp,pri[k],x,y);add(ans,tmp*x*c(n,m,pri[k],k)%mod);}return ans;}
}lu2;ll C(ll n,ll m)
{return mod==1000003 ? lu1.c(n,m):lu2.crt(n,m);
}int main()
{n=read();m=read();tot=read();mod=read();for(int i=1;i<=tot;i++) a[i]=(node){read(),read()};a[++tot]=(node){n,m};sort(a+1,a+tot);if(mod==1000003) lu1.init();else lu2.init();for(int i=1;i<=tot;i++){f[i]=C(a[i].x+a[i].y,a[i].x);for(int j=1;j<i;j++) if(a[j].y<=a[i].y)f[i]=(f[i]-f[j]*C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x)%mod)%mod;f[i]=(f[i]+mod)%mod;}printf("%lld\n",f[tot]);return 0;
}