#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int buf[105];
inline void print(int x,char ch=' '){
	if(x<0) putchar('-'),x=-x;
	int tot=0;
	do{
		buf[++tot]=x%10;
		x/=10;
	}while(x);
	for(int i=tot;i;i--) putchar(buf[i]+'0');
	putchar(ch);
}
const int MAXN=5e3+5;
int n,mod;
int c[MAXN][MAXN],f[MAXN],g[MAXN],pw[MAXN];
signed main(){
	n=read(),mod=read();
	
	for(int i=0;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*4%mod;
	
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n&&(i+j)*2<=n;j++)
			f[(i+j)*2]=(f[(i+j)*2]+c[(i+j)*2][i]*c[i+j*2][i]%mod*c[j*2][j])%mod;
	for(int i=1;i<=n;i++){
		g[i]=f[i];
		for(int j=1;j<i;j++)
			g[i]=(g[i]-f[j]*g[i-j]%mod+mod)%mod;
	}
	
	int ans=(n+1)*pw[n]%mod;
	for(int i=1;i<=n;i++)
		ans=(ans-g[i]*pw[n-i]%mod*(n-i+1)%mod+mod)%mod;
	print(ans);
	return 0;
}