#include <iostream>
#include <cstdio>

using namespace std;

const int NMAX = 201;
const int MOD = 9899;

int n;
int speta1[NMAX][NMAX];
int speta2[NMAX][NMAX];


void sp()
{
    speta1[0][0] = 1;
    speta2[0][0] = 1;
    for(int i=1; i<=NMAX-1; i++)
        for(int j=0; j<=NMAX-1; j++)
        {
            speta1[i][j] = (speta1[i-1][j-1] - (i-1) * speta1[i-1][j])%MOD;
            speta2[i][j] = (speta2[i-1][j-1] + j * speta2[i-1][j])%MOD;
        }
}

void read()
{
    cin>>n;
    sp();
    for(int i=0; i<n; i++)
    {
        int x,n,m;
        cin>>x>>n>>m;
        if(x==1)
            cout<<speta1[n][m];
        else
            cout<<speta2[n][m];
        cout<<endl;
    }
}

int main()
{
    freopen("stirling.in", "r", stdin);
    freopen("stirling.out", "w", stdout);
    read();
}