P12010 【MX-X10-T6】[LSOT-4] Sets

Let the universal set be $U$. An **operation scheme** is defined as assigning to each non-empty subset $S \subseteq U$ a representative element $r(S)$ chosen from $S$. An operation scheme is **good** if and only if for every non-empty subset $S \subseteq U$, it satisfies the following: for any partition of $S$ into $m$ non-empty subsets $A_1, A_2, \ldots, A_m$, there exists $1 \le i \le m$ such that $r(A_i) = r(S)$. Given $U = \{1, 2, \ldots, n\}$, compute the number of **essentially distinct** good operation schemes modulo $1000000087$. Two operation schemes are **essentially distinct** if and only if there exists at least one non-empty subset $S \subseteq U$ where $r(S)$ differs between the two schemes.

A single line containing two positive integers $n, m$.

A single integer, the number of good operation schemes modulo $1000000087$.

**Sample Explanation #1** All schemes are good, so the answer is $1^3 \times 2^3 \times 3 = 24$. **Sample Explanation #2** The six valid schemes are: 1. $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$; 2. $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$; 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$; 4. $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$; 5. $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$; 6. $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$. **Data Range** **This problem uses subtasks with bundled testing.** - Subtask 1 (5 pts): $m = 2$. - Subtask 2 (6 pts): $n \le 4$. - Subtask 3 (10 pts): $n \le 3 \times 10^3$. - Subtask 4 (18 pts): $m = 1$. - Subtask 5 (26 pts): $m \le 3 \times 10^3$. - Subtask 6 (35 pts): No additional constraints. For all test cases: $1 \le m < n \le 2 \times 10^5$. Translation by DeepSeek R1