#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct mat{
    int a[2][2];
};
inline int ksm(int x, int y){
    int ans = 1;
    while(y){
        if(y & 1) ans = (1LL * ans * x) % mod;
        x = (1LL * x * x) % mod; y >>= 1;
    }
    return ans;
}
inline mat operator *(mat x, mat y){
    mat res;
    res.a[0][0] = res.a[0][1] = res.a[1][0] = res.a[1][1] = 0;
    for(int k = 0; k <= 1; ++k){
        for(int i = 0; i <= 1; ++i){
            for(int j = 0; j <= 1; ++j){
                int now = (1LL * x.a[i][k] * y.a[k][j]) % mod;
                res.a[i][j] = (res.a[i][j] + now) % mod;
            }
        }
    }
    return res;
}
inline mat ksm2(mat x, int y){
    mat ans;
    ans.a[0][0] = ans.a[1][1] = 1;
    ans.a[0][1] = ans.a[1][0] = 0;
    while(y){
        if(y & 1) ans = ans * x;
        x = x * x; y >>= 1;
    }
    return ans;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        int n, k, r;
        scanf("%d%d%d", &n, &k, &r);
        if(r == 1 || r == 0){
            puts("0");
            continue;
        }
        int bs = (1LL * (r - 2) * (r - 2)) % mod;
        bs = (bs + (r - 1)) % mod;
        int al = (1LL * k * (n - 1)) % (mod - 1);
        bs = ksm(bs, al);
        if(k == 3){
            int now = (1LL * r * (r - 1)) % mod;
            now = (1LL * now * (r - 2)) % mod;
            now = (1LL * now * bs) % mod;
            printf("%d\n", now);
        }else{
            mat x;
            x.a[0][0] = 0, x.a[0][1] = r - 1, x.a[1][0] = 1, x.a[1][1] = r - 2;
            x = ksm2(x, k - 2);
            int a = (1LL * r * (r - 1)) % mod, b = (1LL * r * (r - 1)) % mod;
            b = (1LL * b * (r - 2)) % mod;
            int ans = (1LL * a * x.a[0][0]) % mod;
            ans = (ans + ((1LL * b * x.a[1][0]) % mod)) % mod;
            ans = (1LL * ans * bs) % mod;
            printf("%d\n", ans);
        }
    }
    return 0;
}