#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1000000007
using namespace std;
ll gt[1000005];
int a[maxn][maxn],n,r,c;
ll g[maxn][maxn],f[maxn][maxn];
int topx,topy,downx,downy;
template<typename T> inline void read(T &x)
{
char c;
bool neg = false;
while (!isdigit(c = getchar()) && c != '-');
x = 0;
if (c == '-')
{
neg = true;
c = getchar();
}
do
{
x = x * 10 + c - '0';
}
while (isdigit(c = getchar()));
if (neg) x = -x;
}
template<typename T> inline void write(T x)
{
if (x < 0)
{
putchar('-');
write(-x);
return;
}
if (x < 10)
{
putchar(char(x + 48));
}
else
{
write(x/10);
putchar(char(48 + x%10));
}
}
template<typename T> inline void writeln(T x)
{
write(x);
putchar('\n');
}
ll cal1(int x,int y)
{
if (x==downx&&y==downy) return 1;
if (f[x][y]!=-1) return f[x][y];
ll res=0;
if (x>downx)res+=1ll*cal1(x-1,y)*gt[y];
if (y>downy)res+=1ll*cal1(x,y-1)*gt[x];
f[x][y]=res;
return res;
}
ll cal2(int x,int y)
{
if (x==topx&&y==topy) return 1;
if (g[x][y]!=-1) return g[x][y];
ll res=0;
if (x<topx) res+=1ll*cal2(x+1,y)*gt[downy-y+1];
if (y<topy) res+=1ll*cal2(x,y+1)*gt[downx-x+1];
f[x][y]=res;
return res;
}
int main()
{
//freopen("Mascots.inp","r",stdin);
cin.tie(0);
cout.tie(0);
read(r);
read(c);
read(n);
topx=1e9,topy=1e9;
for (int i=1; i<=n; ++i)
{
int u,v;
read(u);
read(v);
topx=min(topx,u);
topy=min(topy,v);
downx=max(downx,u);
downy=max(downy,v);
a[u][v]=1;
}
for (int i=1; i<=r; ++i)
for (int j=1; j<=c; ++j)
{
f[i][j]=-1;
g[i][j]=-1;
}
gt[0]=1;
for (int i=1; i<=r*c; ++i)
gt[i]=(gt[i-1]*i)%mod;
ll res=(1ll*cal1(r,c)*cal2(1,1))%mod;
if ((topx!=1||topy!=1)&&(downx!=r||downy!=c))
res=(1ll*res*2)%mod;
res=(1ll*res*gt[(downx-topx+1)*(downy-topy+1)-n])%mod;
cout<<res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
29556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
29556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
29556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
