#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
int Power(int x, int y) {
    int ret = 1;
    while(y) {
        if(y & 1) ret = 1ll * ret * x % MOD;
        y >>= 1;
        x = 1ll * x * x % MOD;
    }
    return ret;
} 
void Do() {
    int n, k, la;
    cin >> n >> k >> la;
    if(la <= 1) {
        cout << 0 << endl;
        return;
    }
    LL A = Power(Power((1ll*la*la-3*la+3)%MOD,n-1),k);
    LL B = Power(la-1,k)+((k&1)?-1:1)*(la-1);
    LL Ans = ((A*B)%MOD+MOD)%MOD;
    cout << Ans << endl;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // init();
    int T;
    cin >> T;
    while(T --) {
        Do();
    }
}