#include <fstream>
const int nr=98999;
using namespace std;
int S[201][201],N,s[201][201],a,b,c;
const int nr1 = 201;
void dets(){
	s[1][1] = 1;
	for (int i = 2; i < nr1;++i)
	for (int j = 1; j <= i; ++j)
		s[i][j] = (s[i - 1][j-1] - (i - 1)*s[i - 1][j])%nr;
}
void detS(){
	S[1][1] = 1;
	for (int i = 2; i <nr1; ++i)
	for (int j = 1; j <= i; ++j)
		S[i][j] = (S[i - 1][j - 1] + j*S[i - 1][j]) % nr;
}
int main(){
	ifstream f("stirling.in");
	ofstream of("stirling.out");
	f >> N;
	dets(); detS();
	for (int i = 0; i < N; ++i){
		f >> a >> b >> c;
		(a == 1) ? of << s[b][c] << "\n":of << S[b][c] << "\n";
	}
}