#include <fstream>

using namespace std;

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

int sp1[1005][1005],sp2[1005][1005];

void SpetaI()
{
    int i,j;
    sp1[1][1]=1;
    for(i=2; i<1005; i++)
    {
        for(j=1; j<=i+1; j++)
            sp1[i][j]=(sp1[i-1][j-1]-(i-1)*sp1[i-1][j])%98999;
    }
}

void SpetaII()
{
    int i,j;
    sp2[1][1]=1;
    for(i=2; i<1005; i++)
    {
        for(j=1;j<=i+1; j++)
            sp2[i][j]=(sp2[i-1][j-1]+j*sp2[i-1][j])%98999;
    }
}

int main()
{
 int T,i,x,n,m;
    fin>>T;
    SpetaI();
    SpetaII();
    for(i=1; i<=T; i++)
    {
        fin>>x>>n>>m;
        if(x==1)
            fout<<sp1[n][m]<<'\n';
        else
            fout<<sp2[n][m]<<'\n';
    }
    return 0;
}