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