#include <fstream>
using namespace std;

ifstream f("stirling.in");
ofstream g("stirling.out");

int i,x,n,m,t,mod;

int s(int a, int b)
{
    if(!a||!b) return 0;
    if(a<b) return 0;
    if(a==1&&b==1) return 1;
    return s(a-1,b-1)-(a-1)*s(a-1,b);
}

int S(int a, int b)
{
    if(!a||!b) return 0;
    if(a<b) return 0;
    if(a==1&&b==1) return 1;
    return S(a-1,b-1)+b*S(a-1,b);
}

int main()
{
    mod=98999;
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>x>>n>>m;
        if(x==1) g<<s(n,m)%mod<<'\n';
        else g<<S(n,m)%mod<<'\n';
    }

    f.close();
    g.close();
    return 0;
}