//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>
#include <string>
using	 namespace std;
using ll = long long int;
fstream f("stirling.in");
ofstream o("stirling.out");
constexpr int mod = 98999;
int n, m, speta, t;

int speta2(int n, int k)
{
	if (n == 0 && k == 0)
	{
		return 1;
	}
	if (k == 0)
	{
		return 1;
	}
	if (n == k)
	{
		return 1;
	}
	return (speta2(n - 1, k - 1) + k * speta2(n - 1, k)) % mod;
}


int speta1(int n, int k)
{
	if (n == k)
	{
		return 1;
	}
	if (n == 0 && k == 0)
	{
		return 1;
	}
	if (k == 0)
	{
		return 0;
	}

	return (speta1(n - 1, k - 1) + (n - 1) * speta1(n - 1, k)) % mod;

}

int main()
{
	f >> t;
	while (t--)
	{
		f >> speta >> n >> m;
		if (speta == 2)
		{
			o << speta2(n, m) << "\n";
		}
		else
		{
			if ((n - m) & 1)
			{
				o << "-" << speta1(n, m) << "\n";
			}
			else
			{
				o << speta1(n, m) << "\n";
			}
		}
	}


}