对于一棵 $n + 1$ 个结点的「平衡树」，枚举其根结点的子树个数 $d$ 和子树大小 $s$。

• 首先要将 $2, 3, \ldots, n + 1$ 这 $n$ 个编号无序地分给 $d$ 个互不区分的（稍后会根据每个子树中的最小结点编号加以区分），大小均为 $s$ 的子树，方案数为 $\dfrac{n!}{d! \cdot (s!)^k}$。
• 接下来，每棵（互相区分的）子树均有 $a_s$ 种不同的结构（$a_s$ 为大小等于 $s$ 的本质不同的「平衡树」的数量），方案数为 $a_s^k$。

因此我们得到了递推式：

$$a_{n + 1} = \sum _{d \cdot s = n} \dfrac{n!}{d! \cdot (s!)^k} \cdot a_s^k$$

根据初始状态 $a_1 = 1$，枚举 $s = 1, 2, \ldots, n - 1$ 和 $d = 1, 2, \ldots, \left\lfloor\dfrac{n - 1}{s}\right\rfloor$ 逐个更新答案即可。

最终的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
const int P = 1e9 + 7;
long long a[N], fc[N], ffc[N];
int divs(int a, int b = 1, int p = P)
{
	if (b % a == 0) return b / a;
	int x = divs(p % a, a - b % a, a);
	return (1ll * x * p + b) / a;
}
int main()
{
	freopen("trees.in", "r", stdin);
	freopen("trees.out", "w", stdout);
	int n;
	cin >> n;
	fc[0] = 1;
	for (int i = 1; i <= n; i++)
		fc[i] = fc[i - 1] * i % P;
	ffc[n] = divs(fc[n]);
	for (int i = n - 1; i >= 0; i--)
		ffc[i] = ffc[i + 1] * (i + 1) % P;
	a[1] = 1;
	for (int y = 1; y <= n; y++)
	{
		a[y] = a[y] * ffc[y] % P;
		long long cur = 1;
		for (int x = y, z = 1; x <= n; x += y, z++)
		{
			cur = cur * a[y] % P;
			long long val = fc[x] * ffc[z] % P;
			a[x + 1] += cur * val % P;
			if (a[x + 1] >= P) a[x + 1] -= P;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans += a[i] * fc[i] % P;
		if (ans >= P) ans -= P;
	}
	cout << ans << endl;
	return 0;
}