#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("stirling.in");
ofstream fout("stirling.out");

typedef long long lint;

const lint modit = 98999;

int t;

//s(n)(k) = -(n-1)*s(n-1,k) + s(n-1,k-1)
lint s[214][214];
void makes(){
	s[0][0] = 1;
	for(int n = 1; n <= 200; ++n){
		for(int k = 1; k <= 200; ++k){
			s[n][k] = -(n-1)*s[n-1][k] + s[n-1][k-1];
			s[n][k] %= modit;
		}
	}
}

//S(n)(k) = k*S(n-1,k) + S(n-1,k-1)
lint S[214][214];
void makeS(){
	S[0][0] = 1;
	for(int n = 1; n <= 200; ++n){
		for(int k = 1; k <= 200; ++k){
			S[n][k] = k*S[n-1][k] + S[n-1][k-1];
			S[n][k] %= modit;
		}
	}
}

int main(){
	// ios_base::sync_with_stdio(false);
	
	makes();
	makeS();
	
	fin >> t;
	for(int i = 0; i < t; ++i){
		int x, n, m;
		fin >> x >> n >> m;
		if(x == 1){
			fout << s[n][m];
		}else{
			fout << S[n][m];
		}
		fout << "\n";
	}
	
	return 0;
}