#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll MOD = 1000000007;
using vll = vector<vector<ll>>;
#define rep(i,n) for(int i=0;i<n;i++)

vll mul(vll a, vll b) {
    ll x = a.size();
    ll y = b.size();
    ll z = b[0].size();
    vll ret(x, vector(z, 0LL));
    for(int i = 0; i < x; i ++) {
        for(int j = 0; j < z; j ++) {
            for(int k = 0; k < y; k ++) {
                ret[i][j] += a[i][k] * b[k][j] % MOD;
                if(ret[i][j] >= MOD) ret[i][j] -= MOD;
            }
        }
    }
    return ret;
}
vll pow(vll a, ll n) {
    vll ret(a.size(), vector(a.size(), 0LL));
    rep(i, a.size())ret[i][i] = 1;
    while(n) {
        if(n & 1) {
            ret = mul(ret, a);
        }
        a = mul(a, a);
        n /= 2;
    }
    return ret;
}

int main(){
    ll t;
    cin >> t;
    rep(_, t){
        ll n,k,l;
        cin >> n >> k >> l;
        ll A = (l-1) + (l-2)*(l-2);
        A %= MOD;
        vll a(1, vector<ll>(1, A));
        auto b = pow(a, (n-1)*k);
        vll c = {{0,1},{l-1, l-2}};
        auto d = pow(c, k);
        vll e = {{l}, {0}};
        auto f = mul(d, e);
        ll ans = b[0][0] * f[0][0];
        cout << ans%MOD << endl;
    }

}