#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, f[1050005], mod, ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> mod;
	for (int i = 1; i <= n; i++)
		f[i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j < i; j++){
			if ((i ^ j) < j)
				f[i] = ((f[i] + f[j] - f[i ^ j]) % mod + mod) % mod;
			else
				f[i] = (f[i] + f[j]) % mod;
		}
	for (int i = 1; i <= n; i++)
		ans = (ans + f[i]) % mod;
	cout << ans;
	return 0;
}

f[i]+=f[j] 可以前缀和，但是 f[i]-=f[i^j] 这部分怎么处理呢