#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int _=1e6+5;
int n,p,l[_],s[_],f[_],c[_];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>p;
	s[0]=f[0]=1;l[0]=-1;
	for(int i=1,x;i<=n;i++){
		l[i]=l[i>>1]+1;x=i^(1<<l[i]);
		if(x&&!c[x]){
			if(x==(1<<l[x]))c[x]=(s[2*x-1]-s[x-1]+p)%p;
			else c[x]=(c[1<<l[x]]+c[x-(1<<l[x])])%p;
		}
		f[i]=(s[i-1]-c[x]+p)%p;
		s[i]=(s[i-1]+f[i])%p;
	}
	cout<<(s[n]+p-1)%p<<'\n';
	return 0;
}