容易发现二叉树。

因为答案只和相对大小有关，所以对于一个子树，给它分配那些点的方案数都是相同的，于是自底向上dp方案数。

#include<bits/stdc++.h>
#define int long long
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=1e6+17;
int mod,siz[N],dep[N],mxd;
int mul[N],inv[N];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;b=b>>1ll;
	}return res;
}
int C(int n,int m){
	if(n<m) return 0;
	int res=mul[n]*inv[m]%mod;
	res=res*inv[n-m]%mod;return res;
}
int Lucas(int n,int m){
	if(n<mod&&m<mod) return C(n,m);
	return (int)(C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod);
}
int n;
void dfs1(int x){
	siz[x]=1;
	if(lc<=n){dfs1(lc);siz[x]+=siz[lc];}
	if(rc<=n){dfs1(rc);siz[x]+=siz[rc];}
}
int dfs(int x){
	if(lc>n||rc>n) return 1;//
	int res=dfs(lc)*dfs(rc)%mod;
	res=res*Lucas(siz[x]-1,siz[lc])%mod;
	return res;
}
signed main(){
	cin >> n >> mod;mul[0]=1;inv[0]=1;
	for(int i=1;i<=N-1;i++){
		mul[i]=mul[i-1]*i%mod;
		inv[i]=qpow(mul[i],mod-2);
	}dfs1(1);int ans=dfs(1);
	cout << ans << '\n';
	
	return 0;
}