#include <iostream>
#include <fstream>

using namespace std;

typedef long long lint;

const int mod = 98999, maxn = 205;

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

int n, q, d, c;
lint a[maxn][maxn];
lint b[maxn][maxn];

void precalc() {
    a[0][0] = 1;
    b[0][0] = 1;
    int i, j;
    for(i = 1; i <= 200; i ++) {
        for(j = 1; j <= 200; j ++) {
            a[i][j] = a[i-1][j-1] - ((i-1) * (a[i-1][j])); a[i][j] %= mod;
            b[i][j] = b[i-1][j-1] + (j * b[i-1][j]); b[i][j] %= mod;
        }
    }
}

int stirling1(int n, int k) {
    return a[n][k];
}

int stirling2(int n, int k) {
    return b[n][k];
}

int main()
{
    precalc();

    f >> n;
    while(n --) {
        f >> q >> d >> c;
        if(q == 1) {
            g << stirling1(d, c) << '\n';
        } else {
            g << stirling2(d, c) << '\n';
        }
    }

    f.close();
    g.close();
    return 0;
}