#include <iostream>
#include <fstream>
 
using namespace std;
 
ifstream fin("stirling.in");
ofstream fout("stirling.out");
 
int C1[201], C2[201]; // C[i] = coeficientu lui x^i
 
int& Dp(int i, int j)
{
    if (i % 2 == 0)
        return C1[j];
    return C2[j];
}
 
int Mod(int x)
{
    if (x >= 0)
        return x % 98999;
    return (x % 98999 + 98999) % 98999;
}
 
int s(int n, int m)
{
    for (int i = 0; i <= n; ++i)
        C1[i] = C2[i] = 0;
 
    C1[0] = 1;
 
    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
            C2[i + 1] = C1[i];
 
        C2[0] = 0;
 
        for (int i = 0; i <= n; ++i)
            C2[i] = Mod(C2[i] + C1[i] * (-k));
 
        for (int i = 0; i <= n; ++i)
            C1[i] = C2[i];
    }
 
    if (n - m % 2 == 0)
        return C1[m];
    return (C1[m] - 98999) % 98999;
}
 
int S(int n, int m)
{
	Dp(1, 1) = 1;
	for (int i = 2; i <= n; ++i)
	{
		for (int j = 1; j <= i; ++j)
		{
			Dp(i, j) = Mod(Dp(i - 1, j) * j + Dp(i - 1, j - 1));
		}
	}
 
    return Dp(n, m);
}
 
int main()
{
    int t;
    fin >> t;
 
    for (int i = 1; i <= t; ++i)
    {
        int x, n, m;
        fin >> x >> n >> m;
 
        if (x == 1)
            fout << s(n, m) << '\n';
        else fout << S(n, m) << '\n';
    }
 
    return 0;
}