#include<cstdio>
using namespace std;
int speta,m=98999,n,s1[212][212],s2[212][212],t;
int main()
{
	freopen("stirling.in","r",stdin);
	freopen("stirling.out","w",stdout);
	s1[0][0]=1;
	s2[0][0]=1;
	for(int i=1;i<=211;i++)
	{
		s2[i][0]=0;
		s2[i][i]=1;
		s1[i][i]=0;
		s1[i][0]=0;
	} 
	for (int i=1;i<=211;i++)
		for (int j=1;j<=211;j++)
		{
			s1[i][j]=(s1[i-1][j-1]-s1[i-1][j]*(i-1))%m;
			s2[i][j]=(s2[i-1][j-1]+s2[i-1][j]*j)%m;
		}
	scanf("%d\n",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d %d %d\n",&speta,&n,&m);
		if(speta==1) printf("%d\n",s1[n][m]);
		else printf("%d\n",s2[n][m]);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}