团队协作

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一个团队有 $N$ 个人。你可以选择任意非空子集参与一项任务；若选中了 $x$ 个人，花费为 $x^k$。

求所有非空子集的花费之和，对 $10^9+7$ 取模。

输入格式

输入一行两个整数 $N,k$。

输出格式

输出答案对 $10^9+7$ 取模后的结果。

样例输入 1

1 1

样例输出 1

1

样例输入 2

3 2

样例输出 2

24

数据范围

对于所有数据，$1\le N\le10^9$，$1\le k\le5000$。