// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include "pilgrimage.h"
#include <bits/stdc++.h>
using namespace std;

#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 1e6;
struct fastmod {
	typedef unsigned long long u64;
	typedef __uint128_t u128;
	int m;
	u64 b;
	fastmod(int m = 2) : m(m), b(((u128)1 << 64) / m) {}
	int reduce(u64 a) {
		u64 q = ((u128)a * b) >> 64;
		int r = a - q * m;
		return r < m ? r : r - m;
	}
} z[N + 5];
struct pii {int x, y;};
namespace solve {
	ll n, m, p;
	inline void Exgcd(ll a, ll b, ll &x, ll &y) {
		if (!b) x = 1, y = 0;
		else Exgcd(b, a % b, y, x), y -= a / b * x;
	}
	inline ll fpm(ll x, ll power, ll Mod) {
		// return 1;
		ll res = 1;
		for (; power; power >>= 1, x = z[Mod].reduce(x * x))
			if (power & 1) res = z[Mod].reduce(res * x);
		return res;
	}
	inline ll fac(ll n, ll pi, ll pk) {
		if (!n) return 1;
		ll res = 1;
		rep (i, 2, pk) if (i % pi) res = z[pk].reduce(res * i);
		res = fpm(res, n / pk, pk);
		rep (i, 2, n % pk) if (i % pi) res = z[pk].reduce(res * i);
		return res * fac(n / pi, pi, pk) % pk;
	}
	inline ll Inv(ll n, ll Mod) {
		ll x, y;
		Exgcd(n, Mod, x, y);
		return (x % Mod + Mod) % Mod;
	}
	inline ll CRT(ll b, ll Mod) {
		return z[p].reduce(z[p].reduce(b * Inv(p / Mod, Mod)) * (p / Mod));
	}
	inline ll factor(ll x, ll Mod) {
		return x ? factor(x / Mod, Mod) + (x / Mod) : 0;
	}
	inline ll Comb(ll n, ll m, ll pi, ll pk) {
		ll k = factor(n, pi) - factor(m, pi) - factor(n - m, pi);
		if (!fpm(pi, k, pk)) return 0;
		return fac(n, pi, pk) * Inv(fac(m, pi, pk), pk) % pk * Inv(fac(n - m, pi, pk), pk) % pk * fpm(pi, k, pk) % pk;
	}
	vector<pii> s;
	inline ll ExLucas(ll n, ll m) {
		ll res = 0, tmp = p;
		if(!siz(s)) {
			rep(i, 2, sqrt(p + .5)) if (!(tmp % i)) {
				ll pk = 1;
				while (!(tmp % i)) pk *= i, tmp /= i;
				res = z[p].reduce(res + CRT(Comb(n, m, i, pk), pk));
				s.PB((pii) {i, pk});
			}
			if (tmp > 1) res = z[p].reduce(res + CRT(Comb(n, m, tmp, tmp), tmp)), s.PB((pii) {tmp, tmp});
		}
		else for(pii x : s) res = z[p].reduce(res + CRT(Comb(n, m, x.x, x.y), x.y));
		return res;
	}
	int ANS (int _n, int _m, int _p) {
		n = _n, m = _m, p = _p;
		return ExLucas(n, m);
	}
}
namespace s2 {
	int fac[N + 5], inv[N + 5], mod;
	int qp(int n, int m = mod - 2) {
		int res = 1;
		for (; m; m >>= 1) {
			if (m & 1) res = res * n % mod;
			n = n * n % mod;
		}
		return res;
	}
	void init() {
		fac[0] = fac[1] = 1;
		rep(i, 2, mod - 1) fac[i] = z[mod].reduce(fac[i - 1] * i);
		// cout << fac[999982] << ' ' << mod << endl;
		inv[mod - 1] = qp(fac[mod - 1]);
		per(i, mod - 2, 0) inv[i] = inv[i + 1] * (i + 1) % mod;
	}
	int C(int n, int m) {return fac[n] * inv[m] % mod * inv[n - m] % mod;}
	int ANS(int n, int m) {
		if(n < m) return 0;
		if(n < mod) return C(n, m);
		return z[mod].reduce(ANS(n % mod, m % mod) * ANS(n / mod, m / mod));
	}
}

int a, b, i2, mod;
int qp(int n, int m = mod - 2) {
	int res = 1;
	for(; m; m >>= 1) {
		if(m & 1) res = z[mod].reduce(res * n);
		n = z[mod].reduce(n * n);
	}
	return res;
}
int phi(int n) {
	int res = n;
	for(int i = 2; i * i <= n; ++i) {
		if(n % i == 0) {
			res = res / i * (i - 1);
			for(; n % i == 0; n /= i);
		}
	}
	if(n > 1) res = res / n * (n - 1);
	return res;
}

#undef int
int T, C[6005][6005];
void init (int o, int p) {
	rep(i, 2, N) z[i] = fastmod(i);
	T = o;
	mod = p;
	a = phi(p) - 1;
	i2 = qp(2, a);
	if(T == 1 || T == 2) {
		rep(i, 0, 6000) {
			C[i][0] = 1;
			rep(j, 1, i) C[i][j] = z[p].reduce(C[i - 1][j - 1] + C[i - 1][j]);
		}
	}
	if(T == 4 || T == 5) s2::mod = p, s2::init();
}
int ask(ll n) {
	if(T == 1 || T == 2) return C[2 * n - 1][n] * n % mod * 2 % mod * qp(i2, 2 * n) % mod;
	else if(T == 4 || T == 5) return s2::ANS(2  * (n % mod) * 2 % mod * qp(i2, 2 * n) % mod* n - 1, n) * (n % mod) * 2 % mod * qp(i2, 2 * n) % mod;
	return solve::ANS(2 * n - 1, n, mod);
}

// signed main() {
// 	// freopen("in1.in", "r", stdin);
// 	// freopen("out.out", "w", stdout);
// 	// cout << calc(666, 64, 2).val;
// 	// return 0;
// 	printf("%lld", ans);
// 	return 0;
// }