#include <bits/stdc++.h>

using namespace std;

ifstream fin("stirling.in");
ofstream fout("stirling.out");

#define MAX 98999

//const int MAX=98999;

int speta_1(int a,int b)
{
	if(a == 0 || b == 0)
		return 0;
	if(a < b)
		return 0;
	if(a == 1 && b == 1)
		return 1;
	return (speta_1(a - 1, b - 1) - (a - 1) * speta_1(a - 1, b))% MAX;
}

int speta_2(int a,int b)
{
	if(a == 0 || b == 0)
		return 0;
	if(a < b)
		return 0;
	if(a == 1 && b == 1)
		return 1;
	return (speta_2(a - 1, b - 1) + b * speta_2(a - 1, b))% MAX;
}

int main()
{
	int cer, a, b, n;

	fin >> n;

	while(n > 0)
	{
		fin >> cer >> a >> b;
		if(cer == 1)
			fout << speta_1(a, b) << '\n';
		if(cer == 2)
			fout << speta_2(a, b) << '\n';
        n--;
	}

	return 0;
}