#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define unsi unordered_set<int>
#define qi queue<int>
#define sti stack<int>
#define pqi priority_queue<int>
#define mii map<int,int>
#define unmii unordered_map<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=1000000+5;
int head[N],ne=0;
ll n,mod;
ll f[N],sz[N];
ll fac[N],inv[N];
ll fst(ll x,ll y){
    ll ans=1;
    while(y){
        if (y&1)ans=ans*x%mod;
        x=x*x%mod;y>>=1;
    }
    return ans;
}
void init(){
    fac[1]=1;int lim=min(n,mod-1);
    for (int i=2;i<=lim;i++)fac[i]=fac[i-1]*i%mod;
    inv[lim]=fst(fac[lim],mod-2);
    for (int i=lim;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll lucas(ll x,ll y){
    if (x<y)return 0;
	if (!x)return 1;
	ll ans=0,xx=x%mod,yy=y%mod;
	if (xx>=yy) ans=fac[xx]*inv[yy]%mod*inv[xx-yy]%mod;
	return lucas(x/mod,y/mod)*ans%mod;
}
int main(){
	freopen ("permzj.in","r",stdin);
	freopen ("permzj.out","w",stdout);
	scanf("%lld%lld",&n,&mod);init();
	f[0]=1;
	for (int i=n;i>=1;i--){
	    int lc=i*2,rc=i*2+1;
	    if (lc>n)lc=0;
	    if (rc>n)rc=0;
	    sz[i]+=sz[lc]+sz[rc]+1;
	    f[i]=lucas(sz[i]-1,sz[lc])*f[lc]%mod*f[rc]%mod;
    }
    printf("%lld\n",f[1]);
    return 0;
}