#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

vector<vector<ll>> mul(vector<vector<ll>> a, vector<vector<ll>> b) {
    vector<vector<ll>> c(a.size());
    for (int i = 0; i < a.size(); i++) c[i].resize(b[0].size());
    for (int i = 0; i < a.size(); i++) for (int j = 0; j < b[0].size(); j++) {
        for (int k = 0; k < a[0].size(); k++) {
            c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
        }
    }
    return c;
}

ll po(ll a, ll b) {
    ll c = 1;
    while (b) {
        if (b % 2) c = c * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return c;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, k, l, z = 1;
        cin >> n >> k >> l;
        ll m = (l * l - 3 * l + 3) % mod;
        z = po(m, n - 1);
        z = po(z, k);
        vector<vector<ll>> a = {{0, 1}, {l - 1, l - 2}}, b = {{1, 0}, {0, 1}};
        while (k) {
            if (k % 2) b = mul(b, a);
            a = mul(a, a);
            k /= 2;
        }
        //cout << b[0][0] << ' ' << b[0][1] << ' ' << b[1][0] << ' ' << b[1][1] << '\n';
        cout << z * b[0][0] % mod * l % mod << '\n';
    }
}