#include <cstdio>
const int M = 500005;
const int B = 1000;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,f[M],g[M],b[M];
void add(int &x,int y) {if((x+=y)>=m) x-=m;}
void solve(int n)
{
	if(n<=1) return ;solve(n>>1);//递归左边
	for(int i=0;i<=n;i++) g[i]=0;
	for(int i=B;i;i--)//去重的过程仍然是拆分数
	{
		for(int j=n;j>=i;j--)
			g[j]=g[j-i];
		for(int j=0;j+i*(j+2)<=n;j++)
			add(g[j+i*(j+2)],f[j]);
		//这里的初始化变成了添加 i 个 j+2 的数字
		//因为要计算 [j+2,i] 内选数和为 j-i 的方案数 
		for(int j=i;j<=n;j++)
			add(g[j],g[j-i]);
	}
	for(int i=(n>>1)+1;i<=n;i++)
		add(f[i],m-g[i]);//正难则反
}
int main()
{
	n=read();m=read();
	for(int i=B;i;i--)
	//此时还在增加的有 i 个数，转移就是整体加 1
	{
		for(int j=n;j>=i;j--) f[j]=f[j-i];f[i]=1;
		//初始化，现在的 i 个数每个值都是 1
		for(int j=i;j<=n;j++) add(f[j],f[j-i]);
		//可以整体增加多次，所以做完全背包
	}
	f[0]=b[0]=1;solve(n);
	for(int i=1;i<=n;i++) b[i]=b[i-1]*2%m;
	for(int i=0;i<n;i++)
		add(ans,1ll*f[i]*b[n-i-1]%m);
	printf("%d\n",(b[n]+m-ans)%m);
}