#include <bits/stdc++.h> using namespace std; //#define int long long #define endl "\n" #define lc(x) T[x].lc #define rc(x) T[x].rc #define pii pair<int,int> #define p1(x) (x).first #define p2(x) (x).second int h[5010][5010]; const int M=1004535809; int f[5010]; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=1ll*res*a%M; a=1ll*a*a%M; x>>=1; } return res; } int n,m,k; inline int w(int i,int j){ register int S=qp(k,i); register int res=1; for(register int p=S-j+1;p<=S&&res;p++) res=1ll*res*p%M; return res; } inline void add(int &x,int y){ x+=y; // if(x>=M)x-=M; if(x<0)x+=M; } signed main() { // freopen("square.in","r",stdin); // freopen("square.out","w",stdout); ios::sync_with_stdio(0); h[0][0]=1; for(register int i=1;i<=5000;i++) for(register int j=1;j<=i;j++) h[i][j]=(h[i-1][j-1]+1ll*j*h[i-1][j]%M)%M; int t; cin>>t; while(t--){ cin>>n>>m>>k; for(int j=1;j<=m;j++){ f[j]=w(j,n); for(int p=1;p<j;p++) if(h[j][p]) add(f[j],-1ll*h[j][p]*f[p]%M); } cout<<f[m]<<endl; } cout.flush(); return 0; } /* */