#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;

using ll = long long ; 

cs int mod = 1e9 + 7;
void add(int &x ,int y) {
    if((x += y) >= mod) x -= mod; 
}
void dec(int &x, int y) {
    if((x -= y) < 0) x += mod; 
}
int mul(int &x, int y) {
    return 1ll * x * y % mod; 
}
int ksm(int a, int b) {
    int c = 1; 
    for(; b; b >>= 1, a = mul(a, a)) 
    if(b & 1) c = mul(c, a);
    return c; 
}
cs int N = 205; 
int T, n, k, a; 

struct mat {
    int a[2][2];
    mat() {
        memset(a, 0, sizeof a);
    }
    mat operator * (cs mat & x) {
        mat y; 
        for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
        for(int k = 0; k < 2; k++)
        add(y.a[i][j], mul(a[i][k], x.a[k][j]));
        return y; 
    }
}; 

mat pow(mat a, int b) {
    mat c; 
    c.a[0][0] = c.a[1][1] = 1; 
    for(; b; b >>= 1, a = a * a)
    if(b & 1) c = c * a;
    return c; 
}

void Main() {
    cin >> n >> k >> a;
    if(a < 2) {
        cout << 0 << '\n';
        return; 
    }
    ll cc = 1ll * a * a - 3ll * a + 3ll; 
    cc = cc % mod; 
    int ww = ksm(cc, 1ll * k * (n - 1) % (mod - 1));
    mat r; 
    // cout << ww << endl;
    r.a[0][0] = a - 2; 
    r.a[0][1] = 1; 
    r.a[1][0] = a - 1; 
    r = pow(r, k - 1); 
    // cout << r.a[0][0] << ' ' << r.a[0][1] << ' ' << r.a[1][0] << ' ' << r.a[1][1] << endl;
    ww = mul(ww, mul(r.a[1][0], a));
    cout << ww << '\n';
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> T; 
    while(T--) Main();
    return 0; 
}