#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long mod=1e9+7;
long long r,c,mul[10000007],dp[3007][3007],ans=0,lx=0,ly=0,rx=0,ry=0,x,y;
int n;
long long ml(long long a,long long b){
if(b==1) return a;
long long res=ml(a,b/2);
if(b%2==0) return (res*res)%mod;
else return (((res*res)%mod)*a)%mod;
}
long long cal(long long k,long long n){
if(k==0 || n==k) return 1LL;
if(k>n) return 0LL;
return (((mul[n]*ml(mul[k],mod-2))%mod)*ml(mul[n-k],mod-2))%mod;
}
signed main(){
//ios_base::sync_with_stdio(0);
cin>>r>>c;
cin>>n;
lx=r;
ly=c;
for(int i=1;i<=n;i++){
cin>>x>>y;
lx=min(lx,x);
ly=min(ly,y);
rx=max(rx,x);
ry=max(ry,y);
}
mul[0]=1;
for(long long i=1;i<=9000000;i++){
mul[i]=mul[i-1]*i;
mul[i]%=mod;
}
dp[0][0]=mul[(rx-lx+1)*(ry-ly+1)-n];
for(int i=0;i<=r-(rx-lx+1);i++){
for(int j=0;j<=c-(ry-ly+1);j++){
dp[i+1][j]=(dp[i+1][j]+dp[i][j]*mul[c-j])%mod;
dp[i][j+1]=(dp[i][j+1]+dp[i][j]*mul[r-i])%mod;
}
}
ans=dp[r-(rx-lx+1)][c-(ry-ly+1)];
ans=(ans*cal(lx-1,r-(rx-lx+1)))%mod;
ans=(ans*cal(ly-1,c-(ry-ly+1)))%mod;
cout<<ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
79 ms |
150780 KB |
Output is correct |
| 2 |
Correct |
53 ms |
150780 KB |
Output is correct |
| 3 |
Correct |
66 ms |
150780 KB |
Output is correct |
| 4 |
Correct |
76 ms |
150780 KB |
Output is correct |
| 5 |
Correct |
66 ms |
150780 KB |
Output is correct |
| 6 |
Correct |
66 ms |
150780 KB |
Output is correct |
| 7 |
Correct |
79 ms |
150780 KB |
Output is correct |
| 8 |
Correct |
59 ms |
150780 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
150780 KB |
Output is correct |
| 2 |
Correct |
59 ms |
150780 KB |
Output is correct |
| 3 |
Correct |
73 ms |
150780 KB |
Output is correct |
| 4 |
Correct |
53 ms |
150780 KB |
Output is correct |
| 5 |
Correct |
56 ms |
150780 KB |
Output is correct |
| 6 |
Correct |
53 ms |
150780 KB |
Output is correct |
| 7 |
Correct |
53 ms |
150780 KB |
Output is correct |
| 8 |
Correct |
56 ms |
150780 KB |
Output is correct |
| 9 |
Correct |
76 ms |
150780 KB |
Output is correct |
| 10 |
Correct |
59 ms |
150780 KB |
Output is correct |
| 11 |
Correct |
63 ms |
150780 KB |
Output is correct |
| 12 |
Correct |
59 ms |
150780 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
79 ms |
150780 KB |
Output is correct |
| 2 |
Correct |
59 ms |
150780 KB |
Output is correct |
| 3 |
Correct |
69 ms |
150780 KB |
Output is correct |
| 4 |
Correct |
56 ms |
150780 KB |
Output is correct |
| 5 |
Correct |
73 ms |
150780 KB |
Output is correct |
| 6 |
Correct |
116 ms |
150780 KB |
Output is correct |
| 7 |
Correct |
59 ms |
150780 KB |
Output is correct |
| 8 |
Correct |
59 ms |
150780 KB |
Output is correct |
| 9 |
Correct |
93 ms |
150780 KB |
Output is correct |
| 10 |
Correct |
139 ms |
150780 KB |
Output is correct |
| 11 |
Correct |
119 ms |
150780 KB |
Output is correct |
| 12 |
Correct |
106 ms |
150780 KB |
Output is correct |
| 13 |
Correct |
53 ms |
150780 KB |
Output is correct |
| 14 |
Correct |
53 ms |
150780 KB |
Output is correct |
| 15 |
Correct |
199 ms |
150780 KB |
Output is correct |
| 16 |
Correct |
113 ms |
150780 KB |
Output is correct |
| 17 |
Correct |
83 ms |
150780 KB |
Output is correct |
| 18 |
Correct |
186 ms |
150780 KB |
Output is correct |
