我们考虑对一个长度为 $n$ 的随机排列反复执行“粘连块打乱”操作，直到变回升序排列的过程。记随机变量 $X$ 为执行打乱操作的次数，目标是计算 $E(n) = \mathbb{E}[X] \bmod (10^9 + 7)$。

首先，任何一次操作结束后，排列会被划分成若干个“粘连块”——也就是那些相邻且数值连续、顺序保持递增的区间。这些块在下一次打乱时会被视为整体。设最终分得 $m$ 个块的方案数记为 $f(n,m)$。

要统计 $f(n,m)$，我们利用两步思路：

• 如何划分成 $m$ 段？ 将 $1,2,\dots,n$ 这 $n$ 个连续整数切成 $m$ 段，每段至少一个数，对应的方案数是“在 $n-1$ 个相邻间隔中选 $m-1$ 个”，方案数为 $\dbinom{n-1}{m-1}$。
• 如何排列这 $m$ 段？ 划分后得到 $m$ 段，每段内部按升序是唯一的，段与段之间可以任意重排序，共 $m!$ 种。

于是组合可得 $f(n,m) = \dbinom {n-1}{m-1}\cdot m!$。

接下来写出期望 $E(n)$ 的递推。在一步打乱操作中，若当前排列分得 $m$ 块，则下一次继续打乱的概率恰好是“得到 $m$ 块”的概率

$$p_{n,m} = \dfrac{f(n,m)}{n!}$$

当 $m=1$ 时，说明已经是一个整体升序块，过程结束；否则，还需要继续至少一次操作。根据全概率公式，

$$E(n) = 1+\sum_{m=2}^n p_{n,m} E(m)$$

其中“+1”来自当前这一次打乱操作，$E(m)$ 表示若分成 $m$ 块后，从 $m$ 块恢复升序的期望步骤。注意右侧包含 $m=n$ 项，此时分成 $n$ 个单元素块（即完全打散，概率 $p_{n,n}=n!/n!=1$），会导致 $E(n)$ 又出现在右侧。我们将它移到左边：

$$E(n)\left(1-p_{n, n}\right)=1+\sum_{m=2}^{n-1} p_{n, m} E(m) $$

因此

$$E(n)=\frac{1+\sum_{m=2}^{n-1} p_{n,m} E(m)}{1-p_{n,n}}=\frac{1+\sum_{m=2}^{n-1} \frac{f(n, m)}{n !} E(m)}{\sum_{k=1}^{n-1} \frac{f(n, k)}{n !}} $$

这里分母 $\sum_{k<n}p_{n,k}$ 就是一次操作后真正“减少块数”的总概率。

用一维数组 $E[,]$ 自小到大填表：

• 初始值 $E(1)=0$；
• 对于 $i=2$ 到 $n$，先累加 $\sum_{m=2}^{i-1} p_{i,m},E[m]$，再除以分母 $\sum_{k=1}^{i-1}p_{i,k}$，加上 1。

直接双重循环是 $O(n^2)$，当 $n\le2000$ 可接受；若要做到 $n\le10^5$，可用分治 FFT 加速。