#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>

typedef long long LL;

using namespace std;

namespace yjf{
	const int N=1000010;
	
	LL f[N];
	
	int main(){
		int n,Mod;
		scanf("%d%d",&n,&Mod);
		
		LL ans=0;
		f[0]=1;
		for(int i=1;i<=n;i++){
			for(int j=0;j<i;j++){
				f[i]+=f[j];
				f[i]%=Mod;
				if((i^j)<j){
					f[i]-=f[i^j];
					f[i]=(f[i]%Mod+Mod)%Mod;
				}
			}
			ans+=f[i];
			ans%=Mod;
		}
		
		printf("%lld\n",ans);
		
		return 0;
	}
}

int main(){
	//freopen("xor.in","r",stdin);
	//freopen("xor.out","w",stdout);
	
	return yjf::main();
}