题目链接

题意：




题解：














AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double,double> pdd;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};

ll fact[maxn],inv1[maxn];
ll Pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
//逆元
ll inv(ll b){
    return Pow(b,mod-2)%mod;
}
ll C(ll n,ll m){
    if(m>n||n<0||m<0)return 0;
    if(m==0||m==n) return 1;
    ll res=(fact[n]*inv1[m]%mod*inv1[n-m])%mod;
    return res;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = fact[i - 1] * i %mod;
    }
    inv1[maxn - 1] = Pow(fact[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--) {
        inv1[i] = inv1[i + 1] * (i + 1) %mod;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    init();
    int _;
    cin>>_;
    while(_--){
        ll n,m,k;
        cin>>n>>m>>k;
        ll ans=0;
        for(int i=0,cur=1;i<k;i++,cur=-cur)
            ans=(ans+cur*C(k,k-i)*(k-i)%mod*Pow(k-i-1,n-1)%mod+mod)%mod;
        for(int i=0;i<k;i++)
            ans=ans*(m-i)%mod*inv(k-i)%mod;
        cout<<ans<<endl;
    }
    return 0;
}