#include <iostream>
#include <fstream>
using namespace std;
ifstream f("stirling.in");
ofstream g("stirling.out");

int n,x,m,T;
const int MOD=98999,NMAX=1001;
int S[NMAX][NMAX],s[NMAX][NMAX];
void speta1()
{
    s[1][1] = 1;

    for(int i = 2;i<NMAX; i++)
        for(int j = 1; j <= i; j++)
            s[i][j] = (s[i-1][j-1]-(i-1) * s[i-1][j]) % MOD;
}

void speta2()
{
    S[1][1] = 1;

    for(int i = 2; i <NMAX; i++)
        for(int j = 1; j <= i; j++)
            S[i][j] = (S[i-1][j-1] + (j * S[i-1][j]) )% MOD;
}
int main()
{
    f>>T;
    speta1();
    speta2();
    while(T--)
    {
        f>>x>>n>>m;
        if(x==1)
            g<<s[n][m];
        else
            g<<S[n][m];
        g<<'\n';
    }
    return 0;
}