#include <cstdio>

using namespace std;

int n=200, t, s[205][205], S[205][205];

void Precalculari()
{
	int i, j;
	s[1][1] = 1;
	S[1][1] = 1;
	for(i=2; i<=n; i++)
		for(j=1; j<=i; j++)
		{
			s[i][j] = (s[i-1][j-1] - (i-1)*s[i-1][j])%98999;
			S[i][j] = (S[i-1][j-1] + j*S[i-1][j])&98999;
		}
}

int main()
{
	freopen ("stirling.in", "r", stdin);
	freopen ("stirling.out", "w", stdout);
	
	Precalculari();
	
	short x, y, z;
	for(scanf("%d", &t); t; t--)
	{
		scanf("%hd%hd%hd", &x, &y, &z);
		if (x==1)
			printf("%d\n", s[y][z]);
		else
			printf("%d\n", S[y][z]);
	}
	
	return 0;
}