#include <fstream>
#define LL long long int
#define MODULO 98999

using namespace std;

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

LL s(LL a, LL b)
{
    if(a==0 || b==0)
        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)))%MODULO;
}

LL S(LL a, LL b)
{
    if(a==0 || b==0)
        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)))%MODULO;
}

int main()
{
    int T,i,x;
    LL n,m;
    in>>T;
    for(i=1; i<=T; i++)
    {
        in>>x>>n>>m;
        if(x==1)
            out<<s(n,m)%MODULO<<'\n';
        else
            out<<S(n,m)%MODULO<<'\n';
    }


    return 0;
}