#include<iostream.h>
#include<fstream.h>
long long put(int n,int m)
{if(m==0)
     return 1;
if(m%2==0)
     return put(n,m/2)*put(n,m/2);
return n*put(n,(m-1)/2)*put(n,(m-1)/2);}

long long fact(int n)
{if(n==0)
     return 1;
return ((n%98999)*(fact(n-1)%98999))%98999;}

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 ((-1)*fact(n-1))%98999;
                 else
                          return fact(n-1)%98999;
          else
                 return ((s(n-1,m-1)%98999)-((((n-1)%98999)*(s(n-1,m)%98999))%98999))%98999;}

long S(int n,int m)
{if(n==m||(m==1&&n>1))
     return 1;
else
     if(m==2&&n>2)
            return (put(2,n-1)-1)%98999;
     else
            if(m==3&&n>3)
                   return (((put(3,n-1)+1)/2)-put(2,n-1))%98999;
            else
if(m==4&&n>4)
     return (((put(4,n-1)-1)/3+put(2,n-1)-put(3,n-1))/2)%98999;
else
if(m==5&&n>5)
     return (((put(5,n-1)-put(4,n-1))-(3*(put(5,n-1)-put(3,n-1))/2)+(put(5,n-1)-put(2,n-1))-((put(5,n-1)-1)/4))/6)%98999;
else
     return ((S(n-1,m-1)%98999)+(m*(S(n-1,m)%98999)))%98999;}

int main()
{int t,n,m,k,i;
ifstream f1("stirling.in");
ofstream f2("stirling.out");
f1>>t;
for(i=1;i<=t;i++)
      {f1>>k>>n>>m;
      if(k==1)
              f2<<s(n,m)%98999<<endl;
      else
              f2<<S(n,m)%98999<<endl;}
f1.close();
f2.close();
return 0;}