#include<iostream>
#include<cstdio> 
#define ll long long

using namespace std;

const int MAXN = 1e6+10;
ll n,MOD,f[MAXN],siz[MAXN],dp[MAXN];
void exgcd(ll A,ll B,ll &X,ll &Y){
	if(!B)X = 1,Y = 0;
	else exgcd(B,A%B,Y,X),Y -= A/B*X;
}
ll C(ll N,ll M){
	if(M > N)return 0;
	ll x = 0,y = 0;
	exgcd(f[M] * f[N - M],MOD,x,y);
	return f[N] * ((x % MOD + MOD) % MOD)% MOD;
}
ll Lucas(ll N,ll M){
	return M ? Lucas(N/MOD,M/MOD) * C(N%MOD,M%MOD) % MOD : 1;
}
void dfs(ll x){
	if(x > n)return ;
	dfs(x << 1);dfs(x << 1 | 1);
	dp[x] = siz[x] = 1;
	if((x << 1) <= n)siz[x] += siz[x << 1];
	if((x << 1 | 1) <= n)siz[x] += siz[x << 1 | 1];
	if((x << 1 | 1) <= n)dp[x] = Lucas(siz[x]-1,siz[x << 1]) * dp[x << 1] * dp[x << 1 | 1] % MOD;
	else if((x << 1) <= n)dp[x] = dp[x << 1];
}
int main(){
	scanf("%lld%lld",&n,&MOD);
	f[0] = 1;
	for(int i = 1 ; i <= 1e6 ; i ++)f[i] = f[i - 1] * i% MOD;	
	dfs(1);
	printf("%lld",dp[1]);
	return 0;
}

会WA 4个数据点，甚至出现了负数？请问代码哪里出锅了？