#include <iostream>
#include <fstream>
using namespace std;

ifstream f("stirling.in");
ofstream g("stirling.out");

const int MOD = 98999,
          MAX = 201;
int stir[MAX + 1][MAX + 1];

void setare_zero(int n)
{
    int i, j;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= n; ++j)
            stir[i][j] = 0;
}

void stirling1(int n, int k)
{
    int i, j;
    stir[0][0] = 1;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= min(i, k); ++j)
            stir[i][j] = (stir[i - 1][j - 1] % MOD + (i - 1) % MOD * stir[i - 1][j] % MOD) % MOD;
    g << stir[n][k];
}

void stirling2(int n, int k)
{
    int i, j;
    stir[0][0] = 1;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= min(i, k); ++j)
            stir[i][j] = (stir[i - 1][j - 1] % MOD + j % MOD * stir[i - 1][j] % MOD) % MOD;
    g << stir[n][k];
}

int main()
{
    int T, x, n, k;
    f >> T;
    while(T--)
    {
        f >> x >> n >> k;
        setare_zero(n);
        if(x == 1)
            stirling1(n, k);
        else
            stirling2(n, k);
        g << '\n';
    }
    f.close();
    g.close();
    return 0;
}