#include <iostream>
#include <fstream>
using namespace std;
const int m = 98999;
void calculare_1(int s[201][201]){
	s[1][1] = 1;
	for(int i = 2; i <= 200; i++){
		for(int j = 1; j<=i; j++){
			s[i][j] = ( s[i-1][j-1] - (i-1)*s[i-1][j])%m;
		}
	}
}

void calculare_2(int S[201][201]){
	S[1][1] = 1;
	for(int i = 2; i <= 200; i++){
		for(int j = 1; j<=i; j++){
			S[i][j] = ( S[i-1][j-1] + j*S[i-1][j])%m;
		}
	}
}

int main(){
	int n, m, x, t, s[201][201], S[201][201];
	ifstream fin("stirling.in");
	ofstream fout("stirling.out");
	fin >> t;
	calculare_1(s);
	calculare_2(S);
	for(int i = 0; i < t; i++){
		fin >> x >> n >> m;
		if(x == 1){
			fout << s[n][m] << '\n';
		}
		if(x == 2){
			fout << S[n][m] << '\n';
		}

	}
	return 0;

}