CF932E Team Work

你有一个由 $N$ 个人组成的团队。对于某项特定任务，你可以选择任意非空子集的人参与。若选择 $x$ 个人参与该任务，所需的花费为 $x^{k}$。 请输出所有非空子集的总花费之和。

输入仅一行，包含两个整数 $N$（$1 \leq N \leq 10^{9}$）表示总人数，$k$（$1 \leq k \leq 5000$）。

输出所有非空子集的总花费对 $10^{9}+7$ 取模后的结果。

在第一个样例中，只有一个非空子集 $\{1\}$，花费为 $1^{1}=1$。 在第二个样例中，共有七个非空子集。 - $\{1\}$，花费 $1^{2}=1$ - $\{2\}$，花费 $1^{2}=1$ - $\{1,2\}$，花费 $2^{2}=4$ - $\{3\}$，花费 $1^{2}=1$ - $\{1,3\}$，花费 $2^{2}=4$ - $\{2,3\}$，花费 $2^{2}=4$ - $\{1,2,3\}$，花费 $3^{2}=9$ 总花费为 $1+1+4+1+4+4+9=24$。 由 ChatGPT 4.1 翻译