#include <bits/stdc++.h>

using namespace std;

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

int n, m, t, c, d[105][105], D[105][105];

int main()
{
    int i, j, k, mod=98999;
    fin>>t;
    for(k=1; k<=t; k++)
    {
        fin>>c>>n>>m;
        if(c==1)
        {
            d[1][1] = 1;
            for( i=2; i<=n; ++i)
                for( j=1; j<=m; ++j)
                    d[i][j] = (d[i-1][j-1] - (d[i-1][j]*(i-1)))%mod;
            fout<<d[n][m]<<"\n";
        }
        if(c==2)
        {
            D[1][1] = 1;
            for( i=2; i<=n; ++i)
                for( j=1; j<=m; ++j)
                    D[i][j] = (D[i-1][j-1] + D[i-1][j]*j)%mod;
            fout<<D[n][m]<<"\n";
        }
    }
    return 0;
}