你有一个 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。