#include <iostream>
#include <fstream>

using namespace std;

long long s1[201][201],s2[201][201],i,j,k,t,n,m,q;

fstream f,g;

int main()
{
    s1[0][0]=1;
    s2[0][0]=1;

    for(i=1;i<=200;i++)for(j=1;j<=i;j++)
        s1[i][j]=s1[i-1][j-1]-(i-1)*s1[i-1][j];

    for(i=1;i<=200;i++)for(j=1;j<=i;j++)
        s2[i][j]=s2[i-1][j-1]+j*s2[i-1][j];

    f.open("stirling.in",ios_base::in);
    g.open("stirling.out",ios_base::out);

    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>q>>j>>k;
        if(q==1)g<<s1[j][k]%98999<<'\n';
        else g<<s2[j][k]%98999<<'\n';
    }
}