题目描述

您有一个团队有 $N$ 人。对于特定任务，您可以选择任何非空的人员子集。拥有的成本 $x$ 人的任务是$x^k$。

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

输入格式

输入行只包含两个整数N$$(1<=N<=10^9)代表总人数和 $k$ $(1<=k<=5000)$。

输出格式

输出所有非空子集模的成本和 $10^9+7$。

题意翻译

给定 $n,k$ ，求： $\sum_{i=1}^n\binom n i \times i^k$ $1 \leq k \leq 5000,1 \leq n \leq 10^9$

输入输出样例

输入 #1

1 1

输出 #1

1

输入 #2

3 2

输出 #3

24

说明/提示

在第一个示例中，只有一个非空子集 $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$ .