<h2>题目大意</h2>

题意：现在有 $n$ 个格子和 $m$ 种颜色，问你恰好将这些花盆染成 $k$ 种颜色，且同种颜色不相邻的方案数。答案对 $10^9+7$ 取模， $n,m, \leq 10^9,k \leq 10^6$

<h2>心路历程</h2>

首先比较 sb 的交了个 $\binom m k k(k-1)^{n-1}$，WA on 2（其实就 $2$ 组数据）...
然后仔细思考一下，发现 $k(k-1)^{n-1}$ 貌似是 $\leq k$ 的？？然后我就叫了个 $\binom m k (k(k-1)^{n-1}-(k-1)(k-2)^{n-1})$，WA on 2。
稍微理性分析了一下发现这样算太 naive 了，然后改了一下 就 A 了。（今天真是意识模糊的一天）

<h2>题解</h2>

首先我们来分析一下第二种方法为什么不对：考虑在 $k(k-1)^{n-1}$ 中使用了 $x$ 种颜色的某一种确定的方案被计算的次数：$\binom k x$。显然 $\binom k x - \binom {k-1} x \neq 1$，所以做法萎了。
于是我重新推了一下式子。。发现设 $f_i$ 表示恰好染 $i$ 种颜色的方案，$g_i$ 表示染了 $\leq i$ 中颜色的方案的话，首先 $g_i = i(i-1)^{n-1}$，然后发现它们之间有关系
$$g_n = \sum_{k = 1}^n \binom n i f_i$$
于是立刻有
$$f_n = \sum_{k=i}^n (-1)^{n-i} \binom n i g_i$$
我们要求的答案就是 $\binom m k f_k$
科普小学知识1：暴力算组合数的复杂度是 $O(m)$ 的，可以使用广义定义 $\binom n m = \frac{n^{\underline m}}{m!}$
科普小学知识2：组合数可以快速算一行。（这个算幼儿园知识了吧我就不说了）
所以这题就是个很 ez 的题了。

/*
 * Author: RainAir
 * Time: 2019-08-27 19:22:27
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int ha = 1e9 + 7;
const int MAXN = 1e6 + 5;

inline int qpow(int a,int n=ha-2){
    if(a < 0) return 0;
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

int cs,n,m,k,f[MAXN];// (m,*)

inline void prepare(){
    f[0] = 1;f[1] = k;
    FOR(i,2,k) f[i] = 1llf[i-1](k-i+1)%ha*qpow(i)%ha;
    f[k] = 1;
}

int C(int n,int m){
    if(n < m) return 0;
    if(!m) return 1;
    int ans = 1,t = 1;
    FOR(i,n-m+1,n) ans = 1llans(i%ha)%ha;
    FOR(i,1,m) t = 1llti%ha;
    return 1llansqpow(t)%ha;
}

inline void Solve(){
    printf("Case #%lld: ",++cs);
    scanf("%lld%lld%lld",&n,&m,&k);
    prepare();int ans = 0;
    FOR(i,1,k){
        ans = (ans + ((f[i]i%haqpow(i-1,n-1)%ha)*((k-i)&1 ? -1 : 1)) + ha)%ha;
    }
    printf("%lldn",ans*C(m,k)%ha);
}

signed main(){
    int T;scanf("%lld",&T);
    while(T--) Solve();
    return 0;
}