题目描述

记全集为 $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)$ 在两个操作方案中不同。

输入格式

仅一行，两个正整数 $n, m$。

输出格式

仅一行，一个整数，表示方案数对 $1000000087$ 取模的结果。

3 1

24

3 2

6

4 3

2592

114514 3

750017326

114514 19198

274658403

提示

【样例解释 #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$。