#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <unordered_set>
#include <assert.h>
#include <bitset>

using namespace std;
#define REP(i, l, r) for(int i = l; i <= r; ++i)
#define PER(i, r, l) for(int i = r; i >= l; --i)
namespace Main {
	const int N = 1e6 + 5;
	int n, mod;
	int f[N];
	void add(int &x, int y) {
		x += y;
		if (x < 0) x += mod;
		if(x >= mod) x -= mod;
	}
	int lg[N];
	int main() {
		ios::sync_with_stdio(false);
		cin.tie(0),cout.tie(0);
		cin >> n >> mod;
		lg[0] = -1;
		for(int i = 1; i <= n; ++i) {
			f[i] = 1;
			add(f[i], f[i - 1]);
			lg[i] = lg[i >> 1] + 1;
			for (int j = 0; (i >> j) > 1; ++j) {
				if((i >> j) & 1) {

					add(f[i], -f[(1 << (j + 1)) - 1]);
					add(f[i], f[(1 << j) - 1]);
				}
			}
			add(f[i], f[i - 1]);
		}
		cout << f[n] << '\n';
		return 0;
	}
}
int main() {
//	freopen("sort.in", "r", stdin);
//	freopen("sort.out", "w", stdout); 
	Main :: main();
	return 0;
} 
/*
5 
4 5 1 2 3
*/