#include<algorithm>#include<iostream>#include<cstdio>usingnamespacestd;
#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> voidchkmin(T & a, T const& b){if(a > b) a = b;}
template <typename T> voidchkmax(T & a, T const& b){if(a < b) a = b;}
constint N = 5010, P = 1004535809;
int S[N][N], n, m, K;
il intpw(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 intadd(constint &x, constint & y){return x + y >= P ? x + y - P : x + y;}
il intrds(constint &x, constint & y){return x - y < 0 ? x - y + P : x - y;}
int S1[N][N], f[N];
il intF(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 voidinit(){
constint 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 voidsolve(){
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);
}
signedmain(){
//freopen("square.in", "r", stdin);//freopen("square.out", "w", stdout);
init();
int T = rd(); while(T--) solve();
return0;
}