#include <bits/stdc++.h>

using namespace std;

ifstream fin("stirling.in");
ofstream fout("stirling.out");
const int mod = 98999;
map<pair<int, int>, int> s1, s2;
int t, op, n, m;

static inline int Calcs(int n, int m) {
    if(!n || !m) return 0;
	if(n < m) return 0;
    
    if(n == 1 && m == 1) return 1;
    if(s1.find({n, m}) != s1.end()) return s1[{n, m}];
    
    int nr = (Calcs(n - 1, m - 1) - (n - 1) * Calcs(n - 1, m)) % mod;
    s1[{n, m}] = nr;
    
    return nr;
}

static inline int CalcS(int n, int m) {
    if(!n || !m) return 0;
	if(n < m) return 0;
    
    if(n == 1 && m == 1) return 1;
    if(s2.find({n, m}) != s2.end()) return s2[{n, m}];
    
    int nr = (CalcS(n - 1, m - 1) + m * CalcS(n - 1, m)) % mod;
    s2[{n, m}] = nr;
    
    return nr;
}

int main() {
    s1[{1, 1}] = s2[{1, 1}] = 1;
    
    fin >> t;
    while(t--) {
        fin >> op >> n >> m;
        if(op == 1) fout << Calcs(n, m) << "\n";
        else        fout << CalcS(n, m) << "\n";
    }

    return 0;
}