#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using str = string;
#define reps(i, a, n) for (ll i = (a); i < ll(n); i++)
#define rep(i, n) reps(i, 0, n)

constexpr ll MOD = ll(1e9) + 7;
ll pow_mod(ll x, ll n) {
    assert(n >= 0);
    assert(n <= (1LL << 40));
    ll r = 1;
    x %= MOD;
    while (n) {
        if (n & 1) r = (r * x) % MOD;
        x = (x * x) % MOD;
        n >>= 1;
    }
    return r;
}

void solve() {
    ll n, k, l;
    cin >> n >> k >> l;
    vector<vector<vector<ll>>> mat(40, vector<vector<ll>>(2, vector<ll>(2)));
    mat[0][0][1] = 1;
    mat[0][1][0] = l - 1;
    mat[0][1][1] = l - 2;
    auto mul = [&](vector<vector<ll>> a, vector<vector<ll>> b) {
        vector<vector<ll>> res(2, vector<ll>(2));
        rep(i, 2) rep(j, 2) rep(k, 2) res[i][j] += a[i][k] * b[k][j], res[i][j] %= MOD;
        return res;
    };
    for (int i = 1; i < 40; i++) {
        mat[i] = mul(mat[i - 1], mat[i - 1]);
    }
    vector<vector<ll>> v(2, vector<ll>(2));
    v[0][0] = v[1][1] = 1;
    for (int i = 0; i < 40; i++)
        if ((k - 1) >> i & 1) v = mul(v, mat[i]);
    ll res = v[1][0] * l % MOD;
    ll val = ((l - 1) * (l - 1) % MOD - (l - 2) + MOD) % MOD;
    val = pow_mod(val, n - 1);
    val = pow_mod(val, k);
    res = res * val % MOD;
    cout << res << endl;
}

int main() {
    ll t = 1;
    cin >> t;
    rep(i, t) solve();
}