#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5009, Mod = 1004535809; int _, n, m, K, S[N][N]; LL f[N]; int get(int n, int m) { if (n - m + 1 <= 0) return 0; LL res = 1; while (m--) res = res * (n--) % Mod; return res; } int main() { freopen("square.in", "r", stdin); freopen("square.out", "w", stdout); S[0][0] = 1; for (int i = 1; i <= 5e3; i++) { for (LL j = 1; j <= i; j++) { S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % Mod; } } scanf("%d", &_); while (_--) { scanf("%d%d%d", &n, &m, &K); LL pK = 1; for (int i = 1; i <= m; i++) { pK = pK * K % Mod, f[i] = 0; for (int j = 1; j < i; j++) { f[i] = f[i] + S[i][j] * f[j]; } f[i]%=Mod; f[i] = (get(pK, n) - f[i] + Mod) % Mod; } printf("%lld\n", f[m]); } fclose(stdin); fclose(stdout); return 0; }