#include<stdio.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;
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)
              if(s(n,m)<0)
                     printf("%ld\n",s(n,m));
              else
                     printf("%ld\n",s(n,m)%98999);
      else
              printf("%ld\n",S(n,m)%98999);}
fclose(stdin);
fclose(stdout);
return 0;}