#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
#define all(v) v.begin(),v.end()
#define pb push_back

void dbg_out() {cerr << endl; }
template< typename H, typename... T> 
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

constexpr int MOD = 1e9+7;

struct mint {
	int x;
	mint(): x(0) {}
	mint(int _x): x(_x%MOD<0?_x%MOD+MOD:_x%MOD) {}
	void operator+=(mint rhs) { x += rhs.x; if(x>=MOD) x-=MOD; }
	void operator-=(mint rhs) { x -= rhs.x; if(x<0) x+=MOD; }
	void operator*=(mint rhs) { x *= rhs.x; x%=MOD; }
	void operator/=(mint rhs) { *this *= rhs.inv(); }
	mint operator+(mint rhs) { mint res=*this; res += rhs; return res; }
	mint operator-(mint rhs) { mint res=*this; res -= rhs; return res; }
	mint operator*(mint rhs) { mint res=*this; res *= rhs; return res; }
	mint operator/(mint rhs) { mint res=*this; res /= rhs; return res; }
	mint inv() { return this->pow(MOD-2); }
	mint pow(int e) {
		mint res(1);
		for(mint p=*this; e>0; e/=2, p*=p) if(e%2)
			res *= p;
		return res;
	}
};

using Z = mint;

void solve() {
	int n, k, _l;
	cin >> n >> k >> _l;
	if(_l <= 2) {
		cout << 0 << '\n';
		return;
	}
	mint l(_l);
	
	mint ans;

	k--;

	mint x = (l - 1);
	mint y = x*x;

	if(k%2 == 0) {
		int h = k / 2;
		ans += (y.pow(h + 1) - 1) / (y - 1);
		ans -= x*(y.pow(h) - 1) / (y - 1);
		ans -= 1;
	} else {
		int h = k / 2;
		ans += x*(y.pow(h + 1) - 1) / (y - 1);
		ans -= (y.pow(h + 1) - 1) / (y - 1);
		ans += 1;
	}
	ans *= l;



	mint ladder = ((l-1) * (l-1) - (l - 2)).pow(n-1).pow(k+1);
	ans *= ladder;

	cout << ans.x << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t; cin >> t;
	while(t--)
		solve();
}