/**
pentru speta intai
demonstratie misto cu numarul de cicluri in permutare
sau inductie (scrii forma si se vede usor)
semnul e dat de (-1)^(n-k) (poti sa incluzi asta in dp)

pentru speta a doua
dp clasic
cum imparti n oameni in k grupe nevide
*/

#include <fstream>

using namespace std;

const int NMAX = 200;
const int MOD = 98999;
int s1[NMAX + 5][NMAX + 5];
int s2[NMAX + 5][NMAX + 5];

int main()
{
    s1[1][1] = s2[1][1] = 1;
    for (int i = 2;i <= 200;++i)
        for (int j = 1;j <= i;++j)
        {
            //int sign = ((i - j) % 2 ? -1 : 1);
            //s1[i][j] = (s1[i - 1][j - 1] + sign * (i - 1) * s1[i - 1][j]) % MOD;
            s1[i][j] = (s1[i - 1][j - 1] - (i - 1) * s1[i - 1][j]) % MOD;
            s2[i][j] = (s2[i - 1][j - 1] + s2[i - 1][j] * j) % MOD;
        }
    ifstream fin("stirling.in");
    ofstream fout("stirling.out");
    int tests;
    fin >> tests;
    while (tests-- > 0)
    {
        int kind, n, m;
        fin >> kind >> n >> m;
        if (kind == 1)
            fout << s1[n][m] << "\n";
        else
            fout << s2[n][m] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}