P12010 【MX-X10-T6】[LSOT-4] 集合

记全集为 $U$。 定义一个操作方案为对每个非空集合 $S \subseteq U$ 选择 $S$ 中任意一个元素作为 $S$ 的代表元，记为 $r(S)$。 一种操作方案是好的当且仅当对任意非空集合 $S \subseteq U$，满足对于任意将其划分为 $m$ 个非空子集的方案 $A_1, A_2, \ldots, A_m$，$\exists 1 \le i \le m, r(A_i) = r(S)$。 求 $U=\{1, 2, \ldots, n\}$ 时的本质不同的好的操作方案数，将答案对 $1000000087$ 取模。 两个操作方案是本质不同的，当且仅当存在某个非空集合 $S \subseteq U$，使得 $r(S)$ 在两个操作方案中不同。

无

无

**【样例解释 #1】** 所有方案都是好的，所以答案为 $1^3 \times 2^3 \times 3 = 24$。 **【样例解释 #2】** $6$ 种方案分别为： $r(\{1, 2, 3\}) = 1$，$ r(\{1, 2\}) = 1$，$ r(\{1, 3\}) = 1$，$ r(\{2, 3\}) = 2$，$ r(\{1\}) = 1$，$ r(\{2\}) = 2$，$ r(\{3\}) = 3$； $r(\{1, 2, 3\}) = 1$，$ r(\{1, 2\}) = 1$，$ r(\{1, 3\}) = 1$，$ r(\{2, 3\}) = 3$，$ r(\{1\}) = 1$，$ r(\{2\}) = 2$，$ r(\{3\}) = 3$； $r(\{1, 2, 3\}) = 2$，$ r(\{1, 2\}) = 2$，$ r(\{1, 3\}) = 1$，$ r(\{2, 3\}) = 2$，$ r(\{1\}) = 1$，$ r(\{2\}) = 2$，$ r(\{3\}) = 3$； $r(\{1, 2, 3\}) = 2$，$ r(\{1, 2\}) = 2$，$ r(\{1, 3\}) = 3$，$ r(\{2, 3\}) = 2$，$ r(\{1\}) = 1$，$ r(\{2\}) = 2$，$ r(\{3\}) = 3$； $r(\{1, 2, 3\}) = 3$，$ r(\{1, 2\}) = 1$，$ r(\{1, 3\}) = 3$，$ r(\{2, 3\}) = 3$，$ r(\{1\}) = 1$，$ r(\{2\}) = 2$，$ r(\{3\}) = 3$； $r(\{1, 2, 3\}) = 3$，$ r(\{1, 2\}) = 2$，$ r(\{1, 3\}) = 3$，$ r(\{2, 3\}) = 3$，$ r(\{1\}) = 1$，$ r(\{2\}) = 2$，$ r(\{3\}) = 3$。 **【数据范围】** **本题采用捆绑测试。** - 子任务 1（5 分）：$m = 2$。 - 子任务 2（6 分）：$n \le 4$。 - 子任务 3（10 分）：$n \le 3 \times 10^3$。 - 子任务 4（18 分）：$m = 1$。 - 子任务 5（26 分）：$m \le 3 \times 10^3$。 - 子任务 6（35 分）：无特殊限制。 对于全部的数据，$1 \le m < n \le 2 \times 10^5$。