f[i]=f[l]*f[r]*C(size[l]+size[r],size[l]).
需要lucas.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000050
using namespace std;
long long n,mod,inv1[maxn],inv2[maxn],f[maxn],size[maxn];
long long f_pow(long long x,long long y)
{
long long ans=,base=x;
while (y)
{
if (y&) ans=(ans*base)%mod;
base=(base*base)%mod;
y>>=;
}
return ans;
}
void get_table()
{
inv1[]=;inv2[]=mod+;
for (long long i=;i<=n;i++)
{
inv1[i]=inv1[i-]*i%mod;
inv2[i]=f_pow(inv1[i],mod-);
}
}
long long comb(long long n,long long m)
{
return inv1[n]*inv2[m]%mod*inv2[n-m]%mod;
}
long long lucas(long long n,long long m)
{
if (!m) return ;
return comb(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main()
{
scanf("%lld%lld",&n,&mod);
get_table();
for (long long i=n;i>=;i--)
{
size[i]=;long long l=,r=;f[i]=;
if ((i<<)<=n) {size[i]+=size[i<<];l=size[i<<];f[i]=f[i]*f[i<<]%mod;}
if ((i<<|)<=n) {size[i]+=size[i<<|];r=size[i<<|];f[i]=f[i]*f[i<<|]%mod;}
f[i]=f[i]*lucas(l+r,l)%mod;
}
printf("%lld\n",f[]%mod);
return ;
}