#include <fstream>

using namespace std;

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

int n,m,i,s[500][500],j,k,a,b,x,s2[500][500];

int main()
{
    n=m=200;
    for(i=1; i<=n; i++)
    {
        s[i][1]=1;
        s[i][i]=1;
    }
    for(i=1; i<=n; i++)
        for(j=2; j<=m; j++)
        {
            s[i][j]=(s[i-1][j-1]%98999+(j*s[i-1][j])%98999);
            s[i][j]%=98999;
        }
    s2[1][1]= 1;
    for( int i=2 ; i<=n ; ++i )
        for( int j=1 ; j<=i ; ++j )
            s2[i][j]= ( s2[i-1][j-1] - (i-1)*s2[i-1][j] )%98999 ;
    fin>>k;
    for(i=1; i<=k; i++)
    {
        fin>>x>>a>>b;
        if(x==2)
            fout<<s[a][b]<<'\n';
        if(x==1)
            fout<<s2[a][b]<<'\n';
    }
    return 0;
}