This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N =9005,mod = 1e9+7;
#define ll long long
ll per[N];
ll mypow(ll x,ll c){
ll ret=1;
while(c){
if(c&1)
ret= (ret*x)%mod;
x = (x*x)%mod;
c>>=1;
}
return ret;
}
ll dp[N][N];
ll solve(int x,int y,int lx,int ly,int a,int b){
if(x==lx && ly==y)return 1;
ll &ret= dp[x][y];
if(ret!=-1)return ret;
ret = 0;
if(y<ly){
ll temp = a+x;
temp = per[temp];
ret = (ret + temp*solve(x,y+1,lx,ly,a,b))%mod;
}
if(x<lx){
ll temp = b+y;
temp = per[temp];
ret= (ret + temp*solve(x+1,y,lx,ly,a,b))%mod;
}
return ret;
}
ll combi(int n,int c){
ll ret= per[n];
ret = (ret *mypow(per[c],mod-2))%mod;
ret = (ret *mypow(per[n-c],mod-2))%mod;
return ret;
}
int main(){
//freopen("input.txt","r",stdin);
per[0]= 1;
for(int i=1;i<N;++i)per[i]=(per[i-1]*i)%mod;
memset(dp,-1,sizeof(dp));
int dx=N,dy =N,ux=0,uy = 0;
int r,c,n;
cin>>r>>c>>n;
for(int i=0;i<n;++i){
int u,v;
cin>>u>>v;
dx= min(dx,u),dy= min(dy,v);
ux= max(ux,u),uy= max(uy,v);
}
int a = ux-dx+1;
int b= uy-dy+1;
int tot = a*b - n;
ll ret = per[tot];
ret = (ret * combi(r-a,dx-1))%mod;
ret = (ret*combi(c-b,dy-1))%mod;
ret= (ret * solve(0,0,r-a,c-b,a,b))%mod;
cout<<ret<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |