#include<stdio.h>
#include<math.h>
long fact(int n)
{if(n==0)
     return 1;
return n*fact(n-1);}

long s(int n,int m)
{if(n==m)
     return 1;
else
     if((n>0&&m==0)||m>n)
          return 0;
     else
          return s(n-1,m-1)-(n-1)*s(n-1,m);}

long S(int n,int m)
{if(n==m||m==1)
     return 1;
else
     if((m==n-1&&n>2)||m==2)
          return (long)(pow(2,n-1))-1;
     else
          return S(n-1,m-1)+m*S(n-1,m);}

int main()
{int t,n,m,k,i;
long p;
freopen("stirling.in","r",stdin);
freopen("stirling.out","w",stdout);
scanf("%d\n",&t);
for(i=1;i<=t;i++)
      {scanf("%d%d%d",&k,&n,&m);
      if(k==1)
              {p=s(n,m);
              if(p>=98999||p<=-98999)
                     printf("%ld\n",p%98999);
              else
                     printf("%ld\n",p);}
      else
              {p=S(n,m);
              if(p>=98999)
                     printf("%ld\n",p%98999);
              else
                     printf("%ld\n",p);}}
fclose(stdin);
fclose(stdout);
return 0;}