ARC065D Shuffling

题意：给出一个长度为 的 串 。

给出 个区间，第 个区间为 ，顺次进行下列操作：

• 任意地排列 的第 到第 个字符。

保证 不降。

请你求出在 次操作后，可以得到多少种不同的 串。答案对 取模。

，时限 。

---

若两个区间 满足 ，则可以丢弃 。这样， 也是不降的。

不难发现，由于 不降，在执行完第 次操作后，范围 就已经确定了。

第 次操作只会确定 这一段。

考虑 ：设 表示处理了前 个区间， 内有 个 的方案数。

记 为 中 的个数。

边界：。

转移：

• 内 的个数必为 。

• 内 的个数至多为 ，至少为 。

  记上下界分别为 ，则对于 ：

  的范围大小上界为 ，故总复杂度为 。

答案为 。