#include <iostream>
#include <map>
using namespace std;
const int mod = 98999;

map<pair<int, int>, int> _s;
map<pair<int, int>, int>::iterator it;
map<pair<int, int>, int> _S;

int Stirling1(int n, int m)
{
	if (n == 0 && m == 0)
		return 1;
	if (n == 0)
		return 0;
	if (m > n)
		return 0;

	if ((it = _s.find(make_pair(n, m))) != _s.end())
		return it->second;
	int v = ((n-1) * Stirling1(n-1, m) + Stirling1(n-1, m-1)) % mod;
	_s[make_pair(n, m)] = v;

	return v;
}

int s(int n, int m)
{
	return Stirling1(n, m) * ( (n - m) % 2 ? -1 : 1);
}

int S(int n, int m)
{
	if (n == m)
		return 1;
	if (m == 0 || m > n)
		return 0;

	if((it = _S.find(make_pair(n, m))) != _S.end())
		return it->second;

	int v = (S(n-1, m-1) + m*S(n-1,m)) % mod;
	_S[make_pair(n, m)] = v;
	return v;
}

int main()
{
	freopen("stirling.in", "r", stdin);
	freopen("stirling.out", "w", stdout);
	int t, x, n, m;

	cin >> t;
	while(t--)
	{
		cin >> x >> n >> m;
		if (x == 1)
			cout << s(n, m) << "\n";
		else
			cout << S(n, m) << "\n";
	}

	return 0;
}