#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


const int MOD=1e9+7;

ll power(ll a,ll p)
{
    ll ret=1;
    while(p)
    {
        if(p&1)ret=(ret*a)%MOD;
        a=(a*a)%MOD;
        p/=2;
    }
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t;
    cin>>t;
    while(t--)
    {
        ll n,k,c;
        cin>>n>>k>>c;
        if(c<2)
        {
            cout<<0<<'\n';
            continue;
        }
        if(c==2&&k%2)
        {
            cout<<0<<'\n';
            continue;
        }
        ll tmp=power((c-2)*(c-3)+(c-2)*2+1,n-1);
        tmp=power(tmp,k);
        tmp*=power(2,MOD-2);
        tmp%=MOD;
        ll rep=c*power(c-1,k-1);
        rep%=MOD;
        if(k%2)
        {
            rep-=(power(c-2,k-1)-1);
        }
        else
        {
            rep-=(power(c-2,k-1)+1);
        }
        rep+=MOD;
        rep%=MOD;

        cout<<(tmp*rep)%MOD<<'\n';

    }
	return 0;
}