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

int qpow(int n,int k){
    int res = 1, base = n;
    while(k){
        if(k&1) res *= base;
        base *= base;
        k >>= 1;
    }
    return res;
}

vector<vector<int>> mulmatrix( vector<vector<int>>& a, vector<vector<int>>& b ) {
    int n=a.size(), m=a[0].size(), k=b[0].size();
    vector<vector<int>> res(n,vector<int>(k,0));
    for( int i=0 ; i < n ; i++ ) {
        for( int j=0 ; j < k ; j++ ) {
            for( int l=0 ; l < m ; l++ ) 
                res[i][j]=(res[i][j]+a[i][l]*b[l][j]%MOD+MOD)%MOD;
        }
    }
    return res;
}

vector<vector<int>> matrixqpow( vector<vector<int>>& a, int k, int y) {
    vector<vector<int>> res={{0},{y, 0}};
    while(k) {
        if( k&1 ) res=mulmatrix(a,res);
        a=mulmatrix(a,a), k>>=1;
    }
    return res;
}

signed main(){
    int L, n, k, y;
    cin >> L;
    while(L--){
        cin >> n >> k >> y;
        vector<vector<int>> turn = {{y-2, y-1}, {1, 0}};
        cout << (matrixqpow(turn, k-1, y))[0][0] % MOD * qpow(qpow((y-1)+(y-2)*(y-2), n-1), k) % MOD << '\n';
    }
}