#include<stdio.h>
#include<conio.h>
#include<time.h>
long long put(long x,long n)
{if(n==0)
     return 1;
if(n%2==0)
     return put(x,n/2)*put(x,n/2);
return x*put(x,(n-1)/2)*put(x,(n-1)/2);}

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==2&&n>2)
          return put(2,n-1)-1;
     else
          return S(n-1,m-1)+m*S(n-1,m);}

int main()
{int t,n,m,k,i;
FILE *f1=fopen("stirling1.txt","r");
FILE *f2=fopen("stirling2.txt","w");
clock_t t1,t2;
t1=clock();
fscanf(f1,"%d\n",&t);
for(i=1;i<=t;i++)
      {fscanf(f1,"%d%d%d",&k,&n,&m);
      if(k==1)
              {if(s(n,m)<0)
                     fprintf(f2,"%ld\n",s(n,m));
              else
                     fprintf(f2,"%ld\n",s(n,m)%98999);}
      else
              fprintf(f2,"%ld\n",S(n,m)%98999);}
t2=clock();
printf("%lf\n",(double)(t2-t1)/CLOCKS_PER_SEC);
fclose(f1);
fclose(f2);
getch();
return 0;}