#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
          if(m==1&&n>1)
                if(n%2==0)
                         return -fact(n-1);
                else
                         return fact(n-1);
          else
                if(m==n-1&&n>6)
                       return s(n,2);
                else
                       if(m==n-2&&n>7)
                              return (3*n-1)*s(n,3)/4;
                       else
                              if(m==n-3&&n>8)
                                      return s(n,2)*s(n,4);
                              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
          if(m==3&&n>3)
                return ((long)(pow(3,n-1))-(long)(pow(2,n))+1)/2;
          else
                if(m==4&&n>4)
                       return ((long)(pow(4,n-1))-(long)(pow(3,n-1))-((long)(pow(4,n-1))-(long)(pow(2,n-1)))+((long)(pow(4,n-1))-1)/3)/2;
                else
                       if(m==5&&n>5)
                              return ((long)(pow(5,n-1))-(long)(pow(4,n-1))-3*((long)(pow(5,n-1))-(long)(pow(3,n-1)))/2+(long)(pow(5,n-1))-(long)(pow(2,n-1))-((long)(pow(5,n-1))-1)/4)/6;
                       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;}