#include <fstream>
#include <algorithm>
using namespace std;

int main()
{
    ifstream fi("stirling.in");
    ofstream fo("stirling.out");
    int n,speta,i,j,k;
    long long s1[201][201],s2[201][201];
    s1[1][1]=s2[1][1]=1;
    for(i=2;i<201;++i)
        for(j=1;j<=i;++j)
        {
            s1[i][j]=(s1[i-1][j-1]-(i-1)*s1[i-1][j]);
            s2[i][j]=(s2[i-1][j-1]-j*s2[i-1][j]);
        }
    fi>>n;
    for(i=1;i<=n;++i)
    {
        fi>>speta>>j>>k;
        if(speta==1)
            fo<<s1[j][k]%98999<<"\n";
        else
            fo<<s2[j][k]%98999<<"\n";
    }
    return 0;
}