#include <bits/stdc++.h>
#include "pilgrimage.h"
#define ll long long
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
const int Maxn=3e3+20;
ll f[Maxn][Maxn<<1];
inline ll ksm(ll x,ll y,ll mod){
	ll sum=1;
	while(y){
		if(y&1) sum=sum*x%mod;
		y=y/2;
		x=x*x%mod;
	}
	return sum;
}
int x,y;
inline void exgcd(int a,int b){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b);
	int t=x;
	x=y;
	y=t-a/b*y;      
}
int mod;
const int Maxm=1e6+10;
int ans[Maxn];
int fac[Maxm],ifac[Maxm];
int p1,p2,p3;
void init(int o, int p){
	mod=p;
	f[0][3005]=1;
	x=y=0;
	exgcd(4,p);
	p1=p3=(x+p)%p;
	x=y=0;
	exgcd(2,p);
	p2=(x+p)%p;
	fr(i,1,3000) fr(j,1,6020) f[i][j]=(f[i-1][j]*p2%p+f[i-1][j-1]*p3%p+f[i-1][j+1]*p1%p)%p;
	fr(n,1,3000) fr(i,1,6020) ans[n]+=1ll*abs(i-3005)*f[n][i]%mod,ans[n]%=mod;
	fac[0]=ifac[0]=1;
	int N=mod-1;
	fr(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[N]=ksm(fac[N],mod-2,mod);
	rf(i,N-1,1) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	// fr(i,2990,3015) printf("f[%lld]=%lld\n",abs(i-3005),f[7][i]);
}
inline int C(long long x,long long y){
	// printf("%lld %lld\n",x,y);
	if(x<mod && y<mod) return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
	return 1ll*C(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
int ask(long long n){
	// printf("%lld %lld\n",n,p2);
	if(n<=3000) return ans[n];
	if(n==1){
		return p2;
	}
	n-=2;
	long long answer;
	answer=ksm(p2,2*n+2,mod);
	// printf("%lld %lld\n",n,answer);
	answer=answer*((2*n)%mod+3)%mod;
	// printf("%lld %lld\n",n,answer);
	answer=answer*C(2*n+1,n)%mod;
	// printf("%lld %lld\n",n,answer);
	return answer;
}