#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;

ll power(ll a, ll pow) {
    ll ret = 1;
    while (pow > 0) {
        if (pow & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        pow /= 2;
    }
    return ret;
}

void solve() {
    ll n, k, c;
    cin >> n >> k >> c;
    if (c == 0 || c == 1) {
        cout << "0\n";
        return;
    }
    
    ll ans = power(c-1, k) + power(c-1, 1) * (k % 2 == 1 ? -1 : 1);
    ans = ans * power((c*c-c*3+3) % MOD, (n-1)*k) % MOD;
    cout << (ans + MOD) % MOD << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int cases;
    cin >> cases;
    while (cases--) solve();
}