#include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=5010,N=15,Mod=1004535809,base=131,mod=1011451423; int _,n,m,k,a[MAXN],jc[MAXN],f[MAXN],h[MAXN][MAXN],ans; inline void slv(){ scanf("%lld%lld%lld",&n,&m,&k); int sum=1; for(int i=1;i<=m;i++){ sum=sum*k%Mod;f[i]=1; for(int j=1;j<=n;j++)f[i]=f[i]*(sum-j+1)%Mod; for(int j=1;j<i;j++){ f[i]-=h[i][j]*f[j]%Mod-Mod; f[i]%=Mod; } // cout<<f[i]<<' '; } //cout<<endl; printf("%lld\n",f[m]); } signed main(){ h[0][0]=1; for(int i=1;i<=5000;i++){ for(int j=1;j<=5000;j++){ h[i][j]=(h[i-1][j-1]+h[i-1][j]*j%Mod)%Mod; //cout<<h[i][j]<<" "; } //cout<<endl; } scanf("%lld",&_);while(_--) slv(); return 0; }