#include <cstdio>
using namespace std;int p;int x, n, m;int sol1[210][210];int sol2[210][210];void generare(){sol1[0][0] = sol2[0][0] = 1;for(int i = 1; i <= 200; i++){sol1[i][i] = 1;sol2[i][i] = 1;for(int j = 1; j <= i; j++){sol1[i][j] = sol1[i - 1][j - 1] - sol1[i - 1][j] * (i - 1);sol1[i][j] %= 98999;sol2[i][j] = sol2[i - 1][j - 1] + sol2[i - 1][j] * j;sol2[i][j] %= 98999;}}}int main(){freopen("stirling.in", "r", stdin);freopen("stirling.out", "w", stdout);scanf("%d", &p);generare();for(int i = 0; i < p; i++){scanf("%d %d %d", &x, &n, &m);if(x == 1){printf("%d\n", sol1[n][m]);}else if(x == 2){printf("%d\n", sol2[n][m]);}}return 0;}