#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, p, k;
int fac[N], inv[N], fin[N];
int dp[N], st[N], l, r;

void init()
{
	fac[0] = 1;
	for(int i = 1;i <= k;i++) fac[i] = fac[i - 1] * i % p;
	inv[0] = 1;
	inv[1] = 1;
	for(int i = 2;i <= k;i++) inv[i] = (p - p / n) * inv[p % n] % p;
	fin[1] = 1;
	for(int i = 2;i <= k;i++) fin[i] = fin[i - 1] * inv[i] % p;
}

int lucas(int a, int b)
{
	if(a == b) return 1;
	if(a < b || b < 0) return 0;
	if(a <= p && b <= p) return fac[a] * fin[b] % p * fin[a - b] % p;
	else return lucas(a / p, b / p) * lucas(a % p, b % p);
}

void dfs(int cur)
{
    st[cur] = 1;
    if ((cur << 1) <= n)
        dfs(cur << 1);
    if ((cur << 1 | 1) <= n)
        dfs(cur << 1 | 1);
}

signed main()
{
	cin >> n >> p;
	k = min(n, p - 1);
	init();
	dp[0] = 1, dp[1] = 1;
	if(n > 2) dfs(2);
	for(int i = 2;i <= n;i++)
	{
		if(st[i]) l++;
		else r++;
		dp[i] = lucas(i - 1, l) * dp[l] % p * dp[r] % p;
	}
	cout<<dp[n]<<"\n";
	return 0;
}