#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
#define il inline
#define re register
#define ll long long
#define rep(i, s, t) for(int i = s; i <= t; i++)
#define per(i, t, s) for(int i = t; i >= s; i--)
il ll rd() {
re int x = 0, f = 1;
re char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -f; ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
template <typename T> void chkmin (T & a, T const& b) {if(a > b) a = b;}
template <typename T> void chkmax (T & a, T const& b) {if(a < b) a = b;}
const int N = 5010, P = 1004535809;
int S[N][N], n, m, K;
il int pw(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = (ll)res * (ll)a % P;
a = (ll)a * (ll)a % P;
b >>= 1;
}
return res;
}
il int add(const int &x, const int & y) {return x + y >= P ? x + y - P : x + y;}
il int rds(const int &x, const int & y) {return x - y < 0 ? x - y + P : x - y;}
int S1[N][N], f[N];
il int F(int x) { //C(K ^ x, n) * n! = (K ^ x) ^ {_n_}
int res = 1, kx = pw(K, x);
rep(i, 1, n) {
res = (ll)res * kx % P;
kx = rds(kx, 1);
}
return res;
}
il void init() {
const int nn = N - 10;
S1[0][0] = 1;
rep(i, 1, nn) rep(j, 1, i)
S1[i][j] = add(S1[i - 1][j - 1], (ll)S1[i - 1][j] * (ll)(i - 1) % P);
}
il void solve() {
n = rd(), m = rd(), K = rd();
rep(i, 0, m) f[i] = F(i);
int sg = (m & 1) ? -1 : 1;
int ans = 0;
rep(i, 0, m) {
if(sg > 0) ans = add(ans, (ll)S1[m][i] * f[i] % P);
else ans = rds(ans, (ll)S1[m][i] * f[i] % P);
sg = -sg;
}
printf("%d\n", ans);
}
signed main() {
//freopen("square.in", "r", stdin);
//freopen("square.out", "w", stdout);
init();
int T = rd(); while(T--) solve();
return 0;
}