1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<cmath> #include<vector> #include<map> #include<queue> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int mod=1e9+7; inline int mo(ll a,int p){ return a>=p?a%p:a; } inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } inline ll gcd(ll x, ll y){ return y==0?x:gcd(y,x%y); } inline ll speed(ll a,ll b,int p){ ll cur=a,anss=1; while(b){ if(b&1) anss=anss*cur%p; cur=cur*cur%p; b>>=1; } return anss%p; } const int MAXN=1e5; bool ipr[MAXN+20]; int cnt,pri[MAXN/5]; void prime(){ int N=sqrt(MAXN)+0.5,mul; memset(ipr,true,sizeof(ipr)); ipr[1]=false; for(int i=2;i<=N;i++){ if(ipr[i]==true){ i==2?mul=1:mul=2; for(int j=i*i;j<=MAXN;j+=i*mul){ ipr[j]=false; } } } for(int i=2;i<=MAXN;i++){ if(ipr[i]==true){ pri[++cnt]=i; } } } int n,m,t; struct E{ int x,y; ll ans; }e[2020]; int cmp(E x,E y){ if(x.x==y.x) return x.y<y.y; return x.x<y.x; } ll jc[200020]={1}; ll fjc[200020]={1}; inline ll C(int nn,int mm){ return mo(mo(jc[nn+mm]*fjc[nn],mod)*fjc[mm],mod); } int main(){ for(int i=1;i<=200000;i++){ jc[i]=jc[i-1]*i%mod; fjc[i]=speed(jc[i],mod-2,mod); } scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=t;i++){ scanf("%d%d",&e[i].x,&e[i].y); e[i].ans=0; } e[t+1]=(E){n,m,0LL}; sort(e+1,e+1+t,cmp); for(int i=1;i<=t+1;i++){ e[i].ans=C(e[i].x-1,e[i].y-1); for(int j=1;j<i;j++){ if(e[j].x<=e[i].x&&e[j].y<=e[i].y){ e[i].ans-=e[j].ans*C(e[i].x-e[j].x,e[i].y-e[j].y); } e[i].ans=(e[i].ans+mod*(ll)mod)%mod; } } printf("%lld\n",e[t+1].ans); return 0; }
|