#include <iostream>
#include <cstring>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 2e5+5;
const int mod = 1e9+7;
int arr[maxN];

long long n, k, r;

struct Mat { int x, y; long long val[3][3]; };
Mat tran, base;
Mat operator*(const Mat &a, const Mat &b) {
  Mat ret; memset(ret.val, 0, sizeof(ret.val));
  orep(i, 0, a.x) {
    orep(j, 0, b.y) {
      orep(z, 0, a.y) {
        ret.val[i][j] = ((a.val[i][z]*b.val[z][j]%mod) + ret.val[i][j]) % mod;
      }
    }
  }
  return ret;
}

long long calR() {
  Mat retm = base, a = tran;
  int kk = k-2;
  while(kk) {
    if (kk&1) { retm = retm*a; }
    kk/=2; a=a*a;
  }
  return retm.val[0][0];
}

long long calL() {
  long long ret = 1, a = ((r-2)*(r-2)%mod+(r-1)%mod) % mod;
  int kk = k*(n-1);
  while(kk) {
    if (kk&1) { ret = ret*a%mod; }
    kk/=2; a=a*a%mod;
  }
  return ret;
}

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  int t; std::cin >> t;
  while(t--) {
    std::cin >> n >> k >> r;
    tran = { 2, 2, {r-2, 1, r-1, 0} };
    base = { 1, 2, r*(r-1), r };
    std::cout << calR() * calL() % mod; NL;
  }


  return 0;
}