Counting_Problem_CC

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
#ifdef  ONLINE_JUDGE
    #define eprintf(...) 42
#else
        #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#endif
clock_t startTime;
double getCurrentTime()
{
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
using namespace std;
const long long mod = (long long) 1e9 + 7;
const int siz = 200005;
long long fact[siz], inv[siz];
long long po(long long x, long long y)
{
    long long ans = 1;
    x %= mod;
    while(y>0)
    {
        if(y&1)
        {
            ans = (ans*x) % mod;
        }
        y /= 2;
        x = (x * x)% mod;
    }
    return ans;
}
long long precomp()
{
    fact[0] = 1;
    inv[0] = 1;
    for(int i=1; i<siz; i++)
    {
        fact[i] = (fact[i-1]*i) % mod;
        inv[i] = po(fact[i], mod-2);
    }
    return 0;
}

long long nCr(long long n, long long r)
{
    if(n<0 || n<r)
    {
        return 0;
    }
    long long ans = fact[n];
    ans *= inv[r]; ans%=mod;
    ans *= inv[n-r]; ans%=mod;
    return ans;
}
int solve()
{
    long long n, m, k;
    cin>>n>>m>>k;
    long long ans = po(m, n);
    for(int i=0; i<=n; i++)
    {
        if(i<k)
        {
            long long sub_ans = nCr(n, i)*po(m-k, i); sub_ans%=mod;
            sub_ans *= po(k-1, n-i); sub_ans%=mod;
            ans -= sub_ans; ans%=mod; ans+=mod; ans%=mod;
        }
                if(i>=k)
        {
            long long sub_ans = nCr(n, i)*po(m-k, k); sub_ans%=mod;
            sub_ans *= po(m-k+1, i-k); sub_ans%=mod;
            sub_ans *= po(k-1, n-i); sub_ans%=mod;
            ans -= sub_ans; ans%=mod; ans+=mod; ans%=mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    startTime = clock();
    precomp();
    while(t--)
    {
        solve();
    }
    eprintf("time = %.5lf\n", getCurrentTime());
    return 0;
}