#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){ int S=qp(k,i); int res=1; for(register int p=S-j+1;p<=S;p++) res=1ll*res*p%M; return res; } signed main() { // freopen("square.in","r",stdin); // freopen("square.out","w",stdout); ios::sync_with_stdio(false); h[0][0]=1; for(short i=1;i<=5000;i++) for(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(short j=1;j<=m;j++){ f[j]=w(j,n); for(short p=1;p<j;p++) if(h[j][p]) f[j]=(f[j]-1ll*h[j][p]*f[p]%M+M)%M; } cout<<f[m]<<endl; } return 0; } /* */