#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll

#define int long long
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
int N, mod, C[5005][5005];
inline void addmod(int &x){ if(x >= mod) x -= mod; }
int dp[5005], pw[5005];
void procedure(){
	N=read(), mod=read();
	pw[0]=1;
	for(int i=1;i<=5000;i++) pw[i]=pw[i-1]*4ll%mod;
	for(int i=0;i<=5000;i++) C[i][0]=1;
	for(int i=1;i<=5000;i++)
		for(int j=1;j<=i;j++)
			addmod(C[i][j]=C[i-1][j]+C[i-1][j-1]);

	int ans = 1ll*(N+1)*pw[N]%mod;
	for(int i=2;i<=5000;i+=2){
		dp[i]=1ll*C[i][i/2]*C[i][i/2]%mod;
		for(int j=2;j<i;j+=2)
			dp[i]=(dp[i]+1ll*(mod-dp[j])*C[i-j][(i-j)/2]%mod*C[i-j][(i-j)/2])%mod;
		if(i<=N) ans = (ans + 1ll*(mod-dp[i])*(N-i+1)%mod*pw[N-i])%mod;
		// cout<<i<<" dp = "<<dp[i]<<endl;
	}
	printf("%lld\n", ans);
}
signed main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=1;
	// math_init();
	// NTT::init();
	while(T--) procedure();
	return 0;
}