#include<fstream>
using namespace std;
#define modulo 98999
int t,n,m,rez,o;

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

int speta1(int n, int m){
    if(n==m)
        return 1;
    if(m>n)
        return 0;
    if(m==0||n==0)
        return 0;
    return (speta1(n-1,m-1)-(n-1)*speta1(n-1,m))%modulo;
}

int speta2(int n, int m){
    if(n==m)
        return 1;
    if(m>n)
        return 0;
    if(m==0||n==0)
        return 0;
    return (speta2(n-1,m-1)+m*speta2(n-1,m))%modulo;
}

int main(){
    cin>>t;
    while(t){
        cin>>o>>n>>m;
        if(o==1)
            cout<<speta1(n,m)<<'\n';
        else
            cout<<speta2(n,m)<<'\n';
        t--;
    }
}