#include <bits/stdc++.h>
#include "pilgrimage.h"
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}

int mod;
ll power(ll p,ll k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}

ll fact[1000005],ifac[1000005];
ll i2;
ll C(ll N,ll M){
	if(N < M || M < 0) return 0;
	if(N < mod) return fact[N] * ifac[M] % mod * ifac[N - M] % mod;
	return C(N / mod,M / mod) * C(N % mod,M % mod) % mod;
}

ll f(ll N){
	if(N % 2 == 0) return (power(2,N) + C(N,N / 2)) * i2 % mod;
	return power(2,N - 1);
}

void init (int taskid, int _p){
	mod = _p;
	i2 = power(2);
	fact[0] = 1;
	rep(i,1,mod - 1) fact[i] = fact[i - 1] * i % mod;
	ifac[mod - 1] = power(fact[mod - 1]);
	per(i,mod - 2,0) ifac[i] = ifac[i + 1] * (i + 1) % mod; 
}

int ask(ll n){
	n *= 2;
	ll ans = 2 * f(n) - 4 * (f(n - 1) + C(n - 1,n / 2));
	ans %= mod;
	ans *= n % mod;
	ans %= mod;
	if(ans < 0) ans += mod;
	ans = ans * power(i2,n + 1) % mod;
	ans = mod - ans;
	return ans;
}