#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)
{
    int d = m;
    m = n - m;
    Dp(0, 0) = Dp(1, 0) = 1;

    for (int i = 1; i <= d; ++i)
    {
        for (int j = 1; j <= m; ++j)
            Dp(i, j) = Mod(Dp(i - 1, j) + Dp(i, j - 1));
    }

    return Dp(d, 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;
}