数论——容斥原理。

从m种颜色中选出k种颜色给n个盒子上色，要求k种颜色都要用到且相邻盒子不能同色，求方法数。

首先，计算C(m,k)为选出k种颜色的方法数。

其次，k种颜色都要用到，换一句话说就是恰好用到k种颜色，显而易见应该转化为至少或者至多再考虑用容斥原理去重。
记f(i)表示至多用i种颜色上色的方案数，容易得到f(i)=i* 图片说明 。
考虑对f(k)去重：最终方案数=至多用k种颜色方案数-至多用k-1种颜色方案数+至多用k-2种颜色方案数-至多用k-3种颜色方案数+...+(-)至多用1种颜色方案数。
注意，其中用i种颜色的方案数，并不仅仅是f(i)，应该是C(k,i)*f(i)，因为要考虑至多用哪i种颜色进行上色，这才是完整的集合。

最后，利用乘法原理将选出k种颜色的方法数与用k种颜色上色的方法数相乘，得到的答案就是：
C(m,k)* (C(k,k)* f(k)-C(k,k-1)* f(k-1)+C(k,k-2)* f(k-2)-...+图片说明* f(1))
其中因为m较大而k较小，且C(m,k)只需求一次，所以可直接计算得到其结果；而C(k,i)则可以由C(k,i+1)推出以避免循环计算。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e5+9;
const ll maxx=1e12+9;

ll n,m,k;

inline ll qpow(ll x,ll t)
{
    ll res=1;
    while(t)
    {
        if(t&1) res=(res*x)%mol;
        t>>=1; x=(x*x)%mol;
    }
    return res;
}
inline ll c(ll n,ll r)
{
    if(n<r) return 0;
    if(n-r<r) r=n-r;
    ll a=1,b=1;
    for(int i=0;i<r;i++)
        a=(a*(n-i))%mol,b=(b*(i+1))%mol;
    return a*qpow(b,mol-2)%mol;
}
int main()
{
    int T; cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        ll tmp=0,C=1;
        for(int i=k;i>=1;i--)
        {
            tmp=(tmp+i*qpow(i-1,n-1)%mol*C%mol+mol)%mol;
            C=-1*C*i%mol*qpow(k-i+1,mol-2)%mol;
        }
        tmp=tmp*c(m,k)%mol;
        cout<<tmp<<endl;
    }
}