← 返回题目列表

Codeforces · 932/E

E. 团队合作

中文机器翻译题面 查看原题

你有一个 N 人的团队。对于特定任务,您可以选择任何非空的人员子集。让 x 个人执行该任务的成本为 xk。

输出所有非空人群子集的成本总和。

输入

仅一行输入包含两个表示总人数的整数 N (1 ≤ N ≤ 109) 和 k (1 ≤ k ≤ 5000)。

输出

输出所有非空子集模 109 + 7 的成本总和。

示例

输入 #1

1 1

输出 #1

1

输入 #2

3 2

输出 #2

24

注意

在第一个示例中,只有一个非空子集 {1},成本为 11 = 1。

在第二个示例中,有七个非空子集。

- {1},成本 12 = 1

- {2},成本 12 = 1

- {1, 2},成本 22 = 4

- {3},成本 12 = 1

- {1, 3},成本 22 = 4

- {2, 3},成本 22 = 4

- {1, 2, 3},成本 32 = 9

总成本为 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24。