#include<bits/stdc++.h> #define up(i,l,r) for(register int i=(l);i<=(r);++i) #define down(i,l,r) for(register 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 #define sub(x,y) ((x-y>=0)?(x-y):(x-y+mod)) 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 calc(int a,int b){ ll res=1; down(i,a,a-b+1){ res=res*1ll*i%mod; if(!res)break; } return res; } void slv(){ n=read(),m=read(),k=read(); int P=k; f[1]=calc(P,n); up(i,2,m){ P=P*1ll*k%mod; f[i]=calc(P,n); up(j,1,i-1)f[i]=sub(f[i],f[j]*1ll*h[i][j]%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; }