#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;

using pii = pair<int, int>;

int powe(int x, int p){
    int res=1;
    while (p>0){if (p&1) res=res*x%MOD; x=x*x%MOD; p>>=1;}
    return res;
}

struct Matrix
{
    int n,m,a[2][2];
    inline Matrix(const int& N=0,const int& M=0)
    {
        n=N; m=M; memset(a,0,sizeof(a));
    }
    inline int* operator [] (const int& x)
    {
        return a[x];
    }
    friend inline Matrix operator * (Matrix A,Matrix B)
    {
        Matrix C(A.n,B.m);
        for (int i=0;i<C.n;++i) for (int j=0;j<C.m;++j)
        for (int k=0;k<A.m;++k) (C[i][j]+=1LL*A[i][k]*B[k][j]%MOD)%=MOD;
        return C;
    }
    friend inline Matrix operator ^ (Matrix A,int p)
    {
        Matrix T(A.n,A.m); for (int i=0;i<T.n;++i) T[i][i]=1;
        for (;p;p>>=1,A=A*A) if (p&1) T=T*A; return T;
    }
};

void solve(){
    int n, k, c; cin >> n >> k >> c;
    if (c<=1) cout << "0\n";
    else if (2==c) cout << (k%2==0 ? 2 : 0) << '\n';
    else{
        Matrix A(2,1),D(2,2);
        A[0][0]=1LL*c*(c-1)%MOD;
        A[1][0]=1LL*A[0][0]*(c-2)%MOD;
        D[0][0]=0; D[0][1]=1;
        D[1][0]=c-1; D[1][1]=c-2;
        A=(D^(k-3))*A;
        int cy=A[1][0];
        int ld = ((c-2)*(c-2)%MOD + (c-1))%MOD;
        cy = cy*powe(ld, (n-1)*k%(MOD-1))%MOD;
        cout << cy << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t; while (t--) solve();
    return 0;
}