#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll mod = 1000000007;

ll modpow(ll b, ll e) {
    ll ans = 1;
    for (; e; b = b * b % mod, e /= 2)
        if (e & 1) ans = ans * b % mod;
    return ans;
}

template<class T, int N> struct Matrix {
typedef Matrix M;
array<array<T, N>, N> d{};
M operator*(const M& m) const {
M a;
rep(i,0,N) rep(j,0,N)
rep(k,0,N) a.d[i][j] += d[i][k]*m.d[k][j];
return a;
}
vector<T> operator*(const vector<T>& vec) const {
vector<T> ret(N);
rep(i,0,N) rep(j,0,N) ret[i] += d[i][j] * vec[j];
return ret;
}
M operator^(ll p) const {
assert(p >= 0);
M a, b(*this);
rep(i,0,N) a.d[i][i] = 1;
while (p) {
if (p&1) a = a*b;
b = b*b;
p >>= 1;
}
return a;
}
};

int main(){
    cin.tie(NULL)->sync_with_stdio(false);

    int t;
    cin >> t;

    while(t--){
        ll n, k, l;
        cin >> n >> k >> l;

        Matrix<ll, 3> A;
        A.d = {{{{0, k-1, k-2}}, {{1, 0, 0}}, {{0, k-1, k-2}}}};

        vector<ll> vec = {1,0,0};

        vec = (A^(k-1)) * vec;
        
        cout << (modpow((n - 1) * ((k - 1) + modpow(k - 2, 2)) % mod, k) * k % mod) * ((vec[1] * (k - 1) % mod + vec[2] * (k - 2) % mod) % mod) % mod  << "\n";
    }
}