#include <cstdio>
#define INFILE "stirling.in"
#define OUTFILE "stirling.out"
#define NMax 256
#define ModP 98999

int S[NMax][NMax], s[NMax][NMax];

using namespace std;

void preprocess()
{
	// cazuri elementare
	S[1][1] = s[1][1] = 1;

	// caz general
	for (int n = 2; n < NMax; ++n)
		for (int k = 1; k <= n; ++k)
		{
			s[n][k] = (s[n - 1][k - 1] - (n - 1) * s[n - 1][k]) % ModP;
			S[n][k] = (S[n - 1][k - 1] + k * S[n - 1][k]) % ModP;
		}
}

int main()
{
	// hai acasa
	preprocess();

	freopen(INFILE, "r", stdin);
	freopen(OUTFILE, "w", stdout);

	int Q, v, n, m;
	scanf("%d", &Q);

	// raspund la intrebari [cred :)]
	while (Q--)
	{
		scanf("%d%d%d", &v, &n, &m);
		
		if (v & 1)
			printf("%d\n", s[n][m]);
		else
			printf("%d\n", S[n][m]);
	}

	return 0;
}