#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;
        //ll a3 = c * (c - 1) * (c - 2);
        ll an = fpow(c - 1, k) + (k&1?-1ll:1ll) * (c - 1);
        an = ((an % P) + P) % P;

        ll t = (c - 2) * (c - 2);
        t %= P;
        t += c - 1;
        t %= P;
        t = fpow(t, n - 1);
        t = fpow(t, k);
        ll ans = an * t % P;
        cout << ans << '\n';
    }
    return 0;
}