#include <bits/stdc++.h>
using namespace std;
#define masterspark ios::sync_with_stdio(0), cin.tie(0),cout.tie(0),cin.exceptions(cin.failbit);

template<class F, class S> ostream &operator<<(ostream &s, pair<F, S> v) { return s << "(" << v.first << ", " << v.second << ")";} 
template<class F, class S> istream &operator>>(istream &s, pair<F, S> &v) { return s >> v.first >> v.second; }
template<class T> istream &operator>>(istream &s, vector<T> &a) { for (auto &x:a) s>>x; return s; }
template<class T> ostream &operator<<(ostream &s, vector<T> &a) { int n=a.size(); if (!n) return s; s<<a[0]; for (int i=1; i<n; i++) s<<' '<<a[i]; return s; }
 
#define int long long
#define pp pair<int, int>
#define ff first
#define ss second

#define forr(i,n) for(int i = 1; i <= n;++i)
#define rep(i,j,n) for(int i = j; i < n;++i)
#define PB push_back
#define PF push_front
#define EB emplace_back
#define all(v) (v).begin(), (v).end()
#define FZ(x) memset(x, 0, sizeof(x)) //fill zero
#define SZ(x) ((int)x.size())
bool chmin(auto &a, auto b) { return (b < a) and (a = b, true); }
bool chmax(auto &a, auto b) { return (a < b) and (a = b, true); }
using i128 = __int128_t;
using i64 = int64_t;
using i32 = int32_t;

const int mod = 1e9 + 7;
void solve(){
    int n, k, l; cin >> n >> k >> l;
    vector<vector<i64>> ans(2, vector<i64> (2, 0));
    
    ans[0][0] = l - 2;
    ans[0][1] = l - 1;
    ans[1][0] = 1;
    ans[1][1] = 0;
    auto mul = [&](vector<vector<i64>> aaa, vector<vector<i64>> bbb) {
        vector<vector<i64>> tmp(2, vector<i64> (2, 0));
        for (i32 i = 0; i < 2; i++) for (i32 l = 0; l < 2; l++) for (i32 k = 0; k < 2; k++) 
        tmp[i][l] += (aaa[i][k] * bbb[k][l]) % mod, tmp[i][l] %= mod;
        return tmp;
    };

    auto ksm = [&](vector<vector<i64>> aaa, int n) {
        vector<vector<i64>> res(2, vector<i64> (2, 0));
        res[0][0] = res[1][1] = 1;
        for (; n; n >>= 1, aaa = mul(aaa, aaa)) if (n & 1) res = mul(res, aaa); 
        return res;
    };
    auto ksm2 = [&](int a, int n) {
        int res = 1;
        for (; n; n >>= 1, a = (a * a) % mod) if (n & 1) res = res * a % mod;
        return res;
    };
    ans = ksm(ans, k-1);
    // int aaaa = (ans[0][1] * l) % mod;
    int aaaa = (ksm2((l-1),n) + ((n&1) ? -1 : 1) * (l-1)) + mod ;
    aaaa %= mod;
    int tmp = (((l * l) % mod - (3 * l) % mod + 3) + mod) % mod;
    aaaa = (aaaa * ksm2(tmp, (n - 1) * k)) % mod;
    cout << aaaa << '\n';
}
signed main()
{
    masterspark
    int t = 1;
    // freopen("stdin","r",stdin);
    // freopen("stdout","w",stdout);
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
} 

/*
     /\_/\
    (= ._.)
    / >  \>
*/