#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

int mod;

int add(LL a, LL b)
{
	return a + b < mod ? a + b : a + b - mod;
}
void updAdd(LL& a, LL b)
{
	a += b;
	if(a >= mod)
		a -= mod;
}
void updSub(LL& a, LL b)
{
	a -= b;
	if(a < 0)
		a += mod;
}
int mult(int a, int b)
{
	return (LL)a * b % mod;
}
int binpow(int a, int n)
{
	int res = 1;
	while(n)
	{
		if(n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

const int N = 5047;
LL f[N];
LL dp[N];
LL C[N][N];

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	int num;
	cin >> num >> mod;
	
	C[0][0] = 1;
	FOR(n, 1, N)
	{
		C[n][0] = 1;
		FOR(m, 1, n + 1)
		{
			C[n][m] = add(C[n - 1][m - 1], C[n - 1][m]);
		}
	}
	FOR(len, 0, N)
	{
		if(len % 2 == 1)
			continue;
		FOR(n, 0, len + 1)
		{
			if(n % 2 == 1)
				continue;
				
			int coef = 1;
			coef = mult(coef, C[len][n]);
			coef = mult(coef, C[n][n / 2]);
			coef = mult(coef, C[(len - n)][(len - n) / 2]);

			
			updAdd(f[len], coef);
		}
	}
	
	
	
	
	
	dp[0] = 1;
	FOR(n, 1, N)
	{
		dp[n] = binpow(4, n);
		FOR(when, 1, n + 1)
		{
			if(when % 2 == 1)
				continue;
			updSub(dp[n], mult(f[when], dp[n - when]));
		}
	}
	
	
	
	LL ans = 0;
	FOR(len, 0, num + 1)
	{
		updAdd(ans, mult(binpow(4, len), dp[num - len]));
	}
	cout << ans << "\n";





	return 0;
}