由于水平和竖直相互独立,所以可以分开计数,最后再用组合数算一下,万年老坑long long
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,k,x,y;
int dpx[1005][1005],dpy[1005][1005],c[1005][1005];
long long sum1[1005],sum2[1005];//这里不用longlong在最后相乘过程中会爆
bool judge(int t,int n)
{
if(t>=1 && t<=n)
return true;
return false;
}
void init()
{
memset(c,0,sizeof(c));
for(int i=0;i<1005;i++)
{
c[i][0]=1;
c[i][i]=1;
}
for(int i=1;i<1005;i++)
{
for(int j=1;j<i;j++)
{
c[i][j]=(c[i-1][j]+c[i-1][j-1])%9999991;
}
}
}
int main()
{
init();
int t;
cin>>t;
for(int te=1;te<=t;te++)
{
cin>>n>>m>>k>>x>>y;
memset(dpx,0,sizeof(dpx));
memset(dpy,0,sizeof(dpy));
memset(sum1,0,sizeof(sum1));
memset(sum2,0,sizeof(sum2));
dpx[0][x]=1;
dpy[0][y]=1;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
for(int s=-2;s<=2;s++)
{
if(s==0) continue;
int t=j+s;
if(!judge(t,n))continue;
dpx[i][t]=(dpx[i][t]+dpx[i-1][j])%9999991;
}
}
}
for(int i=1;i<=k;i++)
{
for(int j=1;j<=m;j++)
{
for(int s=-2;s<=2;s++)
{
if(s==0) continue;
int t=j+s;
if(!judge(t,m))continue;
dpy[i][t]=(dpy[i][t]+dpy[i-1][j])%9999991;
}
}
}
for(int i=0;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
sum1[i]=(dpx[i][j]+sum1[i])%9999991;
//cout<<dpx[i][j]<<" ";
}
//cout<<sum1[i]<<endl;
//cout<<endl;
}
for(int i=0;i<=k;i++)
{
for(int j=1;j<=m;j++)
{
sum2[i]=(dpy[i][j]+sum2[i])%9999991;
}
}
long long ans=0;
for(int i=0;i<=k;i++)
{
long long t=c[k][i]*((sum1[i]*sum2[k-i])%9999991)%9999991;
ans=(ans+t)%9999991;
}
cout<<"Case #"<<te<<":"<<endl;
cout<<ans<<endl;
}
return 0;
}