#include <fstream>
#define MOD 9899
#define LIMIT 200

using namespace std;

long long s[205][205], S[205][205];

void stirling1()
{
    s[1][1] = 1;
    for(int i = 2; i <= LIMIT; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            s[i][j] = (s[i-1][j] * (i - 1) - s[i-1][j-1] + MOD) % MOD;
        }
    }
}

void stirling2()
{
    S[1][1] = 1;
    for(int i = 2; i <= LIMIT; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            S[i][j] = (S[i-1][j] * j + S[i-1][j-1]) % MOD;
        }
    }
}

int main()
{
    /// stirling de speta I s[n][m] = s[n-1][m] * (n-1) + s[n-1][m-1]
    /// in cate moduri pot distribui N persoane in M taxiuri, contand cine dupa cine intra
    /// formal nr de permutari cu exact M cicluri (fiecare taxi e un ciclu)
    /// speţa I, s(n,m), ca fiind coeficienţii dezvoltării  x(x-1)...(x-n+1) = (suma de la m=0, m<=n) s(n,m) * x^k

    /// stirling de speta II S[n][m] = S[n-1][m] * m + S[n-1][m-1]
    ///in cate moduri pot distribui N persoane in M taxiuri :) (contand doar ce persoane in ce taxiuri sunt la final)
    /// formal speţa a II-a, S(n,m), ca fiind numărul de partiţionări ale unei mulţimi de n elemente în m submulţimi nevide.

    ifstream cin("stirling.in");
    ofstream cout("stirling.out");

    stirling1();
    stirling2();

    int T,X,N,M;
    cin>>T;
    while(T--)
    {
        cin>>X>>N>>M;
        if(X == 1)
        {
            cout<<s[N][M]<<'\n';
        }
        else
        {
            cout<<S[N][M]<<'\n';
        }
    }
    return 0;
}