首先按照题意我们可以模拟出来一个小根堆，这样我们就把数组转化为了一棵树。
考虑任意一棵子树，它至多有两个儿子，至少有零个儿子。
先求出以(i)号点为根的子树的节点数，记为(s_i)
这棵子树填入(s_i)个不相同的数的答案记为(f_i)
我们从(1 sim n)排列里选出了任意(s_i)个数，想填入这棵树中。
其中左子树需要(s_{l})个数。(f_i)乘上(C_{s_i}^{s_{l}})，再乘上(f_l,f_r)
即(f_i = C_{s_i}^{s_l} * f_l * f_r)
组合数取模可能要卢卡斯定理。
还有一种思想:
我们有(n)个数，对整棵树来说有(n!)种方法填入。
考虑去重，对于每棵子树，一共有(s_i)个不同的数填入其中，最小的数有且仅有一个，且最小数必须填在根上。
因此答案要除以(s_i)。对于每棵树都有这样的去重。
最终答案即为(frac{n!}{prod_{i=1}^{n} s_i})
#include<bits/stdc++.h>
using namespace std;
int n,m;
int inv[1000005],s[1000005];
long long ans;
int main(){
scanf("%d%d",&n,&m);
inv[0] = inv[1] = 1; for(int i = 2; i <= n; ++ i) inv[i] = 1ll * (m - m / i) * inv[m % i] % m;
for(int i = 1; i <= n; ++ i) s[i] = 1; for(int i = n; i > 1; -- i) s[i / 2] += s[i];
ans = 1; for(int i = 1; i <= n; ++ i) ans = ans * i % m * inv[s[i]] % m; printf("%lld
",ans);
return 0;
}