#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <vector>

#include <set>

#include <map>

#include <queue>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e6 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const int EPS = 1e-8;

int inv[N];

void init(int n)	{

	inv[1] = 1;

	for (int i=2; i<=n; ++i)	{

		inv[i] = (MOD - MOD / i) * 1ll * inv[MOD%i] % MOD;		//inv[n]

	}

}

int pow_mod(int x, int n, int p)	{

	int ret = 1;

	while (n)	{

		if (n & 1)	ret = ret * 1l * x % p;

        x = x * 1ll * x % p;

        n >>= 1;

	}

	return ret;

}

int f(int n, int k)	{

	if (!k)	return 0;

	else	return k * 1ll * pow_mod (k-1, n-1, MOD) % MOD;

}

int main(void)	{

	init (1000000);

	int T, cas = 0;	scanf ("%d", &T);

	while (T--)	{

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

		ll ans = 0;	int res = 1;

		for (int i=1; i<=k; ++i)	{

			res = res * 1ll * (k - i + 1) % MOD * inv[i] % MOD;

			if (k - i & 1)	{

				ans -= res * 1ll * f (n, i) % MOD;

				if (ans < 0)	ans += MOD;

			}

			else	{

				ans += res * 1ll * f (n, i) % MOD;

				if (ans >= MOD)	ans -= MOD;

			}

		}

		for (int i=1; i<=k; ++i)	{

			ans = ans * 1ll * (m - i + 1) % MOD * inv[i] % MOD;

		}

		printf ("Case #%d: %lld\n", ++cas, ans);

	}

	return 0;

}