#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

const int dim = 1005;
int t, x, n, m;
int s[dim][dim], S[dim][dim];

int main ()
{
	freopen ("stirling.in", "r", stdin);
	freopen ("stirling.out", "w", stdout);
	
	s[0][0] = S[0][0] = 1;	
	for (n = 1; n < dim; n++)
		for (m = 1; m <= n; m++)
		{
			s[n][m] = (s[n-1][m-1] - (n-1) * s[n-1][m]) % 98999;
			S[n][m] = (S[n-1][m-1] + m * S[n-1][m]) % 98999;
		}
	
	scanf ("%d", &t);
	while (t --)
	{
		scanf ("%d%d%d", &x, &n, &m);
		if (x == 1)
			printf ("%d\n", s[n][m]);
		if (x == 2)
			printf ("%d\n", S[n][m]);
	}
	
	
	return 0;
}