$$【组合数学】专题笔记目录$$

首先，把这个序列转化为一棵树，让这棵树满足小根堆性质。
然后考虑树上 DP，设 $f_u$ 为 $u$ 子树的方案数。
则显然有 $f_u = C_{sz_u - 1} ^{sz_{ls}} \times f_{ls} \times f_{rs}$，其中 $ls$ 是 $u$ 的左儿子，$rs$ 是右儿子，$sz_u$ 表示 $u$ 子树大小。
上面这个转移方程的含义就是：填完 $u$，在剩下的 $sz_u - 1$ 个数内，选出 $sz_{ls}$ 个分给左子树，剩下的给右子树。由于选出的数肯定可以离散化成一个排列的形式，所以一定可以找到方案满足题目条件。
至于左右子树的方案数就是递归下去子问题了。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 15;
int n, mod;
int dp[N], sz[N];
int fac[N], inv[N];

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

void init(int x) {
    fac[0] = 1;
    for (int i = 1; i <= x; i++) fac[i] = (fac[i - 1] * 1ll * i) % mod;
    inv[x] = qmi(fac[x], mod - 2);
    for (int i = x - 1; i >= 0; i--) inv[i] = (inv[i + 1] * 1ll * (i + 1)) % mod;
}

int C(int n, int m) {
    if (n < m) return 0;
    return ((fac[n] * 1ll * inv[m]) % mod * 1ll * inv[n - m]) % mod;
}

int lucas(int a, int b) {
    if (a < mod && b < mod) return C(a, b);
    return (C(a % mod, b % mod) * 1ll * lucas(a / mod, b / mod)) % mod;
}

void dfs(int u) {
    if (u > n) {
        sz[u] = 0; dp[u] = 1;
        return;
    }
    dfs(u << 1); dfs(u << 1 | 1);
    sz[u] = sz[u << 1] + sz[u << 1 | 1] + 1;
    dp[u] = ((lucas(sz[u] - 1, sz[u << 1]) * 1ll * dp[u << 1] % mod) * 1ll * dp[u << 1 | 1]) % mod;
}

int main() {
    scanf("%d%d", &n, &mod);
    init(min(n, mod - 1));
    dfs(1);
    // for (int i = 1; i <= n; i++) cout << sz[i] << ' ' << dp[i] << endl;
    printf("%d\n", dp[1]);
    return 0;
}