#include<bits/stdc++.h>
#include "pilgrimage.h"
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=3e3;

int inv2,inv4,Mod,f[Maxn+5][Maxn*2+5];

inline int exgcd(int a,int b,int &x,int &y)
{
	if(!b) {x=1,y=0; return a;}
	int res=exgcd(b,a%b,y,x);
	y=y-a/b*x; return res;
}
inline int Inv(int x)
{
	int hzh,rub; exgcd(x,Mod,hzh,rub);
	return (hzh%Mod+Mod)%Mod;
}

void init(int o, int p)
{
	Mod=p,inv2=Inv(2),inv4=Inv(4);
	f[0][Maxn]=1;
	For(i,1,Maxn) For(j,Maxn-i,Maxn+i)
		f[i][j]=(1ll*f[i-1][j-1]*inv4%Mod+1ll*f[i-1][j]*inv2%Mod+1ll*f[i-1][j+1]*inv4%Mod)%Mod;
}

int ask(long long n)
{
	int res=0;
	For(i,Maxn-n,Maxn+n) res=(res+1ll*f[n][i]*abs(i-Maxn)%Mod)%Mod;
	return res;
}