manasa_and_combinatorics_xorfire

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

long long pwr(long long a, long long b, long long md)
{
    long long ret = !b ? 1 : pwr(a, b >> 1, md);
    return ret * ret % md * (b & 1 ? (a % md) : 1) % md;
}

int valu(long long n, long long p)
{
    int ct = 0;
    for(long long pp = p; n >= pp; ct += n / pp, pp *= p);
    return ct;
}

long long go(long long n, long long p)
{
    if(n <= 1) return 1;
    long long q = n / p, r = n % p;
    long long ret = (q & 1) ? (p-1) : 1;
    for(int i = 2; i <= r; ++i) ret = ret * i % p;
    return ret * go(q, p) % p;
}

int main()
{
    int t; cin >> t;
    while(t--)
    {
        long long n; cin >> n;
        if(n <= 5)
        {
            int ret[] = {0, 1, 4, 21, 121, 728};
            cout << ret[n] << '\n';
            continue;
        }

        long long p = 99991, c = valu(3 * n, p);
        c -= valu(n - 1, p) + valu(2 * n + 1, p);

        long long m = n % p;
        c += ((m * m + m + 2) % p == 0);
        m = n;
        while(m % p == 0) m /= p, --c;
        m = n + 1;
        while(m % p == 0) m /= p, --c;

        if(c > 0) { puts("0"); continue; }
        m = n % p, m = (3 * m * m + 3 * m + 6) % p;

        long long num = m * go(3 * n - 1, p) % p;
        long long den = go(2 * n + 2, p) * go(n-1, p) % p;
        cout << num * pwr(den, p-2, p) % p << '\n';
    }
    return 0;
}