#include<fstream>
using namespace std;
ifstream f("stirling.in");
ofstream g("stirling.out");
int t,s,n,m;
const int MOD=98999;
int sp1(int n,int m)
{
    if(!n||!m)
      return 0;
    if(n<m)
      return 0;
    if(n==1&&m==1)
      return 1;
    return(sp1(n-1,m-1)-(n-1)*sp1(n-1,m))%MOD;
}
int sp2(int n,int m)
{
    if(!n||!m)
      return 0;
    if(n<m)
      return 0;
    if(n==1&&m==1)
        return 1;
    return(sp2(n-1,m-1)+m*sp2(n-1,m))%MOD;
}
int main()
{
    f>>t;
    while(t--)
    {
        f>>s>>n>>m;
        if(s==1)
          g<<sp1(n,m)<<"\n";
        else
          g<<sp2(n,m)<<"\n";
    }
    return 0;
}