CF932E.Team Work

You have a team of N people. For a particular task, you can pick any non-empty subset of people. The cost of having x people for the task is x__k.

Output the sum of costs over all non-empty subsets of people.

你有一支由 $N$ 人组成的团队。对于某项特定任务，你可以任选一个非空子集的人员参与。若安排 $x$ 人执行该任务，则其成本为 $x^k$。

请输出所有非空子集对应的成本之和。

Only line of input contains two integers N (1 ≤ N ≤ 109) representing total number of people and k (1 ≤ k ≤ 5000).

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

Output the sum of costs for all non empty subsets modulo 109 + 7.

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

In the first example, there is only one non-empty subset {1} with cost 11 = 1.

In the second example, there are seven non-empty subsets.

- {1} with cost 12 = 1

- {2} with cost 12 = 1

- {1, 2} with cost 22 = 4

- {3} with cost 12 = 1

- {1, 3} with cost 22 = 4

- {2, 3} with cost 22 = 4

- {1, 2, 3} with cost 32 = 9

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 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$。