#include <fstream>
#include <algorithm>
using namespace std;
long long s[201][201],S[201][201];
int main()
{
    ifstream fi("stirling.in");
    ofstream fo("stirling.out");
    int n,speta,i,j,k;
    s[1][1]=S[1][1]=1;
    for(i=2;i<201;++i)
        for(j=1;j<=i;++j)
            s[i][j]=(s[i-1][j-1]-(i-1)*s[i-1][j]);
    for(i=2;i<201;++i)
        for(j=1;j<=i;++j)
            S[i][j]=(S[i-1][j-1]-j*S[i-1][j]);
    fi>>n;
    for(i=1;i<=n;++i)
    {
        fi>>speta>>j>>k;
        if(speta==1)
            fo<<s[j][k]%98999<<"\n";
        else
            fo<<S[j][k]%98999<<"\n";
    }
    return 0;
}