#include <bits/stdc++.h>
#include "pilgrimage.h"
using namespace std;
const int N = 1e6 + 5;
int Id;
int P,inv2;
int fac[N],ifac[N];
inline void init_fac(int n)
{
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[1] = 1;
	for(int i = 2;i <= n;i++) ifac[i] = 1ll * ifac[P % i] * (P - P / i) % P;
	ifac[0] = 1;
	for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
}
inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
inline int Lucas(long long n,long long m)
{
	if(n < P && m < P) return C(n,m);
	else return 1ll * Lucas(n / P,m / P) * C(n % P,m % P) % P;
}
int Bi[6005][6005];
inline void init_Brute(int n)
{
	Bi[0][0] = 1;
	for(int i = 1;i <= n;i++)
	{
		Bi[i][0] = Bi[i][i] = 1;
		for(int j = 1;j < i;j++)
			Bi[i][j] = (Bi[i - 1][j - 1] + Bi[i - 1][j]) % P;
	}
}
inline int qpow(int a,long long b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
void init(int o,int p)
{
	Id = o;P = p;inv2 = (P + 1) / 2;
	if(Id <= 2) init_Brute(6002);
	else init_fac(P - 1);
}
int ask(long long n)
{
	if(n == 1) return inv2;
	if(n == 2) return 3ll * inv2 * inv2 % P;
	if(n == 3) return 15ll * inv2 % P * inv2 % P * inv2 % P * inv2 % P;
	int res = qpow(inv2,2 * n - 2);
	n -= 2;
	if(Id <= 2) res = 1ll * res * Bi[2 * n + 1][n] % P * (2 * n + 3) % P;
	else res = 1ll * res * Lucas(2 * n + 1,n) % P * (2 * n % P + 3) % P;
	return res;
}