#include <iostream>
#include <fstream>
using namespace std;
int t,n,m,speta,s[201][201],S[201][201];
ifstream fi("stirling.in");
ofstream fo("stirling.out");
void precalculare_s()
{   int i, j;
	s[1][1]=1;
	for(i=2; i<201; i++)
		for(j=1; j<=i; j++)
			s[i][j]=(s[i-1][j-1]-(i-1)*s[i-1][j])%98999;
}

void precalculare_S()
{   int i, j;
	S[1][1]=1;
	for(i=2; i<201; i++)
		for(j=1; j<=i; j++)
			S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%98999;
}

int main()
{
    precalculare_s();
    precalculare_S();
    fi>>t;
    while(t)
    {   fi>>speta>>n>>m;
        if (speta==1)
            fo<<s[n][m]<<'\n';
        if(speta==2)
            fo<<S[n][m]<<'\n';
        t--;
    }
    return 0;
}