#include <fstream>

using namespace std;

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

int t, n, m, x, s[205][205], S[205][205];

void stirling1();
void stirling2();

int main()
{
    stirling1();
    stirling2();

    fin>>t;

    int i;

    for(i=1; i<=t; i++)
        {
        fin>>x>>n>>m;
        if(x==1)
            fout<<s[n][m]%98999<<'\n';
            else
            fout<<S[n][m]%98999<<'\n';
        }
    return 0;
}


void stirling1()
{   int i, j;
    s[1][1]= 1;
    for(i=2; i<205; i++)
        for(j=1; j<=i ; j++)
            s[i][j]=s[i-1][j-1]-(i-1)*s[i-1][j];
}

void stirling2()
{   int i, j;
    S[1][1]=1;
    for(i=2; i<205; i++)
        for(j=1; j<=i; j++)
            S[i][j]=S[i-1][j-1]+j*S[i-1][j];
}