#include <fstream>
using namespace std;
ifstream f("stirling.in");
ofstream g("stirling.out");
int sp1[201][201],sp2[201][201];

void sp1create ()
{
	sp1[0][0]=1;
	for (int i=1;i<=200;i++)
		for (int j=1;j<=200;j++)
			sp1[i][j]=(sp1[i-1][j-1]-(i-1)*sp1[i-1][j])%98999;
}
void sp2create()
{
	sp2[0][0]=1;
	for (int i=1;i<=200;i++)
		for (int j=1;j<=200;j++)
			sp2[i][j]=(sp2[i-1][j-1]+j*sp2[i-1][j])%98999;
}
int main ()
{
	int x,y,z,n;
	sp1create();
	sp2create();
	f>>n;
	for (int i=1;i<=n;i++)
	{
		f>>x>>y>>z;
		if (x==1) g<<sp1[y][z]<<'\n';
		else g<<sp2[y][z]<<'\n';
	}
return 0;
}