#include <cstdio>

using namespace std;

int i,j,k,l,m,n;
int v1[205][205],v2[205][205];

int main()
{
    freopen("stirling.in","r",stdin);
    freopen("stirling.out","w",stdout);
    v1[1][1]=1;
    for(i=2;i<=200;i++)
        for(j=1;j<=i;j++)
            v1[i][j]=(v1[i-1][j-1]-(i-1)*v1[i-1][j])%98999;
    v2[1][1]=1;
    for(i=2;i<=200;i++)
        for(j=1;j<=i;j++)
            v2[i][j]=(v2[i-1][j-1]+(j*v2[i-1][j]))%98999;
    scanf("%d",&n);
    while(n>0)
    {
        n--;
        scanf("%d %d %d",&i,&j,&k);
        if(i==1)printf("%d\n",v1[j][k]);
        if(i==2)printf("%d\n",v2[j][k]);
    }
    fclose(stdin);
    fclose(stdout);
}