#include <iostream>

#include <stdio.h>

#include <string.h>

/*

题意：相当于在一个m*n的矩形网格里放k个相同的石子，问有多少种方法？

      限制条件：每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都得有石子。

思路：

    直接求的话会比较麻烦，反过来想：

    设总方案数为S，A={第一行没有石子}，B={最后一行没有石子}，C={第一列没有石子}，D={最后一列没有石子}

    利用容斥原理，先求|A并B并C并D|，然后再用|s|-|A并B并C并D|，即为答案。

    而对于有r行，t列，摆放k个石子的方案数为C(r*t,k)。

*/

using namespace std;

const int maxn=;

const int mod=;

long long c[maxn*maxn][maxn*maxn];

int t,m,n,k;

void init(){

    memset(c,,sizeof(c)); //先初始化为0，因为在计算容斥原理的时候，很有可能会出现C(i,j)(j>i)的情形，此时应该值为0

    c[][]=;

    for(int i=;i<maxn*maxn;i++){     //求出组合数

        c[i][]=;

        for(int j=;j<i;j++)

            c[i][j]=(c[i-][j-]+c[i-][j])%mod;

        c[i][i]=;

    }

}

int main()

{

    long long ans,tmp;

    init();

    scanf("%d",&t);

    for(int i=;i<=t;i++){

        ans=;

        scanf("%d%d%d",&m,&n,&k);

        if(k>m*n||k<)

            ans=;

        else{

            //先求|A并B并C并D|，由于只有四个元素，所以直接写出式子了

            ans=(*c[(m-)*n][k]+*c[m*(n-)][k])%mod;

            tmp=((c[(m-)*n][k]+*c[(m-)*(n-)][k]%mod)%mod+c[(n-)*m][k])%mod;

            ans=(ans-tmp+mod)%mod;

            ans=(ans+*c[(m-)*(n-)][k])%mod;

            ans=(ans+*c[(m-)*(n-)][k])%mod;

            ans=(ans+mod-c[(m-)*(n-)][k])%mod;

            ans=(c[m*n][k]-ans+mod)%mod;  //最后再用所有总的方案数减去ans值，即为最后要求的答案

        }

        printf("Case %d: %lld\n",i,ans);

    }

    return ;

}

#include <iostream>

#include <stdio.h>

#include <string.h>

/*

题意：相当于在一个m*n的矩形网格里放k个相同的石子，问有多少种方法？

      限制条件：每个格子最多放一个石子，所有石子都要用完，并且第一行、最后一行、第一列、最后一列都得有石子。

思路：

    直接求的话会比较麻烦，反过来想：

    设总方案数为S，A={第一行没有石子}，B={最后一行没有石子}，C={第一列没有石子}，D={最后一列没有石子}

    利用容斥原理，先求|A并B并C并D|，然后再用|s|-|A并B并C并D|，即为答案。

    而对于有r行，t列，摆放k个石子的方案数为C(r*t,k)。

*/

using namespace std;

const int maxn=;

const int mod=;

int C[maxn*maxn][maxn*maxn];

int t,m,n,k;

void init(){

    memset(C,,sizeof(C)); //先初始化为0，因为在计算容斥原理的时候，很有可能会出现C(i,j)(j>i)的情形，此时应该值为0

    C[][]=;

    for(int i=;i<maxn*maxn;i++){     //求出组合数

        C[i][]=;

        for(int j=;j<i;j++)

            C[i][j]=(C[i-][j-]+C[i-][j])%mod;

        C[i][i]=;

    }

}

int main()

{

    init();

    scanf("%d",&t);

    for(int i=;i<=t;i++){

        int sum=;

        scanf("%d%d%d",&m,&n,&k);

        //枚举所有16种搭配方式，s=0表明是总的方案数

        //由于最后我们求的是补给的个数，所以在用容斥原理的时候稍作修改：

        //原本奇数个集合是加，改为减；偶数个集合是减，改为加

        for(int s=;s<;s++){

            int b=,r=n,c=m; //b统计该方案数对应的集合的个数，r和c是可以放置的行列数

            if(s&){

                b++;

                r--;

            }

            if(s&(<<)){

                b++;

                r--;

            }

            if(s&(<<)){

                b++;

                c--;

            }

            if(s&(<<)){

                b++;

                c--;

            }

            if(b&)

                sum=(sum+mod-C[r*c][k])%mod;  //奇数个集合，做减法

            else

                sum=(sum+C[r*c][k])%mod;  //偶数个集合，做加法

        }

        printf("Case %d: %d\n",i,sum);

    }

    return ;

}