#include <bits/stdc++.h>

#ifdef LOCAL
using std::cerr;

#else

#endif

#define F first
#define S second
#define pb push_back
#define ALL(x) begin(x), end(x)

using namespace std;
using pii = pair<int, int>;
using ll = long long;
const ll P = 1e9 + 7;

ll fpow(ll a, ll ti) {
    if (ti < 1) return 1;
    int tmp = fpow(a, ti>>1);
    tmp *= tmp;
    tmp %= P;
    if (ti & 1) return tmp * a % P;
    return tmp;
}

ll n, k, c;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tc = 1;
    cin >> tc;
    while (tc--) {
        cin >> n >> k >> c;
        if (n <= 3) {
            ll a3 = c * (c - 1) * (c - 2);
            ll t = (c - 1) + (c - 2) * (c - 2);
            t %= P;
            t = fpow(t, n - 1);
            t = fpow(t, k);
            ll ans = a3 * t % P;
            cout << ans << '\n';
            continue;
        }
        ll a3 = c * (c - 1) * (c - 2);
        ll an = c * fpow(c-1, 3) % P * (fpow(c - 1, n - 3) - 1) * fpow(c - 2, P - 2) % P;
        an = ((an % P) + P) % P;
        ll t = (c - 1) + (c - 2) * (c - 2);
        
        t %= P;
        t = fpow(t, n - 1);
        t = fpow(t, k);
        ll ans = an * t % P;
        cout << ans << '\n';
    }
    return 0;
}