#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define m_p make_pair #define p1 first #define p2 second #define p_b push_back using namespace std; typedef long long ll; const int mod=1004535809; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,k,h[5005][5005],f[5005]; void init(){ h[0][0]=1; up(i,1,5000)up(j,1,i)h[i][j]=(h[i-1][j-1]+h[i-1][j]*1ll*j%mod)%mod; } int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } int calc(int a,int b){ ll res=1; down(i,a,a-b+1)res=res*1ll*i%mod; return res; } void slv(){ n=read(),m=read(),k=read(); f[1]=calc(qpow(k,1),n); up(i,2,m){ f[i]=calc(qpow(k,i),n); up(j,1,i-1)f[i]=(f[i]-f[j]*1ll*h[i][j]%mod+mod)%mod; }printf("%d\n",f[m]); }int main(){ // freopen("square.in","r",stdin); // freopen("square.out","w",stdout); init(); int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; }