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


const int MOD=1e9+7;
#define row vector<ll>
#define matrix vector<row>
matrix zero(int n,int m)
{
     matrix ret=matrix(n,row(m,0));
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<m;j++)
         {
             ret[i][j]=0;
         }
     }
     return ret;
}
matrix id(int n)
{
    matrix ret=zero(n,n);
    for(int i=0;i<n;i++)ret[i][i]++;
    return ret;
}
matrix mul(const matrix &a,const matrix &b)
{
    matrix ret=zero(a.size(),b[0].size());
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j<b[0].size();j++)
        {
            for(int k=0;k<b.size();k++)
            {
                ret[i][j]+=a[i][k]*b[k][j];
                ret[i][j]%=MOD;
            }
        }
    }
    return ret;
}
matrix power(const matrix &a,int p)
{
    if(!p)return id(a.size());
    if(p&1)return mul(power(a,p-1),a);
    return power(mul(a,a),p/2);
}
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;
}

ll calc(int x,int lst,int rem)
{
    if(rem==0)return 1;
    ll ret=0;
    for(int i=1;i<=9;i++)
    {
        if(i==lst)continue;
        if(i==x&&rem==1)continue;
        ret+=calc(x,i,rem-1);
    }
    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)%MOD,n-1);

        tmp=power(tmp,k);
        //tmp*=power(2,MOD-2);
        tmp%=MOD;
        ll rep=c*power(c-1,k-1);
        rep%=MOD;
        matrix mtx=zero(2,2),p=zero(2,2);
        mtx[0][1]=1;
        p[0][0]=MOD-1;
        p[1][0]=MOD-(c-1);
        p[1][1]=(c-1);
        //cout<<rep<<endl;
        mtx=mul(mtx,power(p,k-2));

        rep+=(c*mtx[0][0])%MOD;
        rep+=MOD;
        rep%=MOD;
        //cout<<rep<<" "<<mtx[0][0]<<" "<<calc(9,9,29999)<<endl;
        cout<<(tmp*rep)%MOD<<'\n';

    }
	return 0;
}