#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("stirling.in");
ofstream fout("stirling.out");

int s[201][201],S[201][201];

int stirling_I()
{
    s[1][1]= 1;
    for( int i=2 ; i< 201 ; ++i )
        for( int j=1 ; j<= i ; ++j )
            s[i][j]= ( s[i-1][j-1] - (i-1)*s[i-1][j] )% 98999 ;
}
int stirling_II()
{
    S[1][1] = 1;
    for( int i = 2 ; i< 201 ; ++i )
        for( int j = 1 ; j<= i ; ++j )
            S[i][j]= ( S[i-1][j-1] + j*S[i-1][j] )% 98999 ;
}

int main()
{
    int n,x,y,z;
    stirling_I();
    stirling_II();
    fin >> n;
    while(n--)
    {
        fin >> x >> y >> z;
        if(x == 1)
            fout << s[y][z]<< endl;
        else
            fout << S[y][z]<< endl;

    }



    return 0;
}