/*
 * e_049_stirling.cpp
 *
 *  Created on: Jun 1, 2015
 *      Author: Marius
 */

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

namespace e_049_stirling_nms
{
    const int N = 200;
    const int M = 200;

    int s1[N + 1][M + 1], s2[N + 1][M + 1];

    void calculate_stirlings(int modulo)
    {
        //initializations
        for (int n = 0; n <= N; n++)
        {
            s2[n][n] = s1[n][n] = 1;
            s2[n][0] = s1[n][0] = 0;
        }

        //dynamic programming
        for (int n = 1; n <= N; n++)
            for (int m = 1; m <= M; m++)
            {
                if (m < n)
                {
                    s1[n][m] = s1[n - 1][m - 1] - (n - 1) * s1[n - 1][m];
                    s2[n][m] = m * s2[n - 1][m] + s2[n - 1][m - 1];
                }
                else if (m > n)
                {
                    s1[n][m] = s2[n][m] = 0;
                }
                
                s1[n][m] %= modulo;
                s2[n][m] %= modulo;
            }
    }
}

int main()
{
    using namespace e_049_stirling_nms;

    calculate_stirlings(98999);

    ifstream ifs("stirling.in");
    ofstream ofs("stirling.out");
    int T;
    ifs >> T;
    for (int t = 1; t <= T; t++)
    {
        int s, n, m;
        ifs >> s >> n >> m;

        if (s == 1)
            ofs << s1[n][m] << '\n';
        else
            ofs << s2[n][m] << '\n';
    }
    ifs.close();
    ofs.close();

    return 0;
}