/**

题目：2016-2017 ACM-ICPC CHINA-Final H    Great Cells

链接：http://codeforces.com/gym/101194

题意：给定n*m的矩形，a[i][j]的数据范围为[1,k]；

如果a[i][j]是自己所在行和所在列最大的（唯一最大的），那么这个格子就是great cell；

令Ag表示有g个great cell的矩形数量。

求： sigma[g=0,n*m](g+1)*Ag mod(1e9+7);

思路：

原式可以拆成sigma[g=0,n*m]g*Ag mod(1e9+7) + sigma[g=0,n*m]Ag mod(1e9+7);

第二个式子显然是所有矩阵数量，即：k^(n*m)；

第一个式子：

注意g*Ag不要拆开，看做整体相当于求期望值，只不过舍去了分母。所以等价于求每一个格子是great cell的期望值。

所以所有格子的期望值之和就是第一个式子结果；

sigma[i=1,k]Pow(i-1,n+m-2)*Pow(k,(n-1)*(m-1))*(n*m) mod(1e9+7); i的值表示选定的格子是great cell的值，那么同行同列的n+m-2个格子就是i-1中选取。

剩下的格子(n-1)*(m-1)个都从k中选取。 总共n*m个格子的期望值之和。每个格子期望值都是一样的。

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<set>

#include<cstring>

#include<cmath>

using namespace std;

typedef pair<int,int> P;

typedef long long LL;

const int N = 1e5+;

const int mod = ;

const int INF = 0x3f3f3f3f;

int n, k, m;

LL Pow(LL x,int y)

{

    LL p = ;

    while(y)

    {

        if(y&) p = p*x%mod;

        x = x*x%mod;

        y>>=;

    }

    return p;

}

int main()

{

    int T, cas=;

    cin>>T;

    while(T--)

    {

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

        LL sum = ;

        for(int i = k; i >= ; i--){

            sum = (sum+Pow((LL)i-,n+m-))%mod;

        }

        sum = sum*Pow((LL)k,(n-)*(m-))%mod;

        sum = sum*n*m%mod;

        sum = (sum+Pow((LL)k,n*m))%mod;

        printf("Case #%d: %I64d\n",cas++,sum);

    }

    return ;

}