Description

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.

Input Format

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

Output Format

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

3 1

24

3 2

6

4 3

2592

114514 3

750017326

114514 19198

274658403

Hint

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