转载
code:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1000000007;
inline int QuickPow(int x, int r)
{
int ret = 1;
for (; r; r >>= 1)
{
if (r & 1) ret = (LL)ret * x % mod;
x = (LL)x * x % mod;
}
return ret;
}
int main()
{
int T;
scanf("%d", &T);
for (int kase = 1; kase <= T; ++kase)
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
int mult = QuickPow(k, (n - 1) * (m - 1)), ans = 0;
for (int i = 1; i <= k; ++i)
ans = (ans + (LL)QuickPow(i - 1, n + m - 2) * mult) % mod;
ans = (LL)ans * (n * m) % mod;
ans = (ans + QuickPow(k, n * m)) % mod;
printf("Case #%d: %d\n", kase, ans);
}
return 0;
}