#include <fstream>
using namespace std;
ifstream in("stirling.in");
ofstream out("stirling.out");
const int N = 1002, R = 98999;
int s[N][N], S[N][N];
void get1(){
    s[1][1] = 1;
    for(int i=2;i<N;i++)
        for(int j=1;j<=i;j++)
            s[i][j] = (s[i-1][j-1] - (i-1) * s[i-1][j]) % R;
}
void get2(){
    S[1][1] = 1;
    for(int i=2;i<N;i++)
        for(int j=1;j<=i;j++)
            S[i][j] = (S[i-1][j-1] + j * S[i-1][j]) % R;
}
int main()
{
    int T, C, n, m;
    get1();
    get2();
    in>>T;
    for(int q=1;q<=T;q++){
        in>>C>>n>>m;
        if(C == 1)
            out<<s[n][m]<<"\n";
        else
            out<<S[n][m]<<"\n";
    }
    in.close();
    out.close();
    return 0;
}