# 「Codeforces 932E」Team Work【数论】

Time Limit: 2 Sec Memory Limit: 512 MB

### Description

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.

### Input

The only line of input contains two integers $N$ ($1 \leqslant N \leqslant 10^9$) representing total number of people, and $k$ ($1 \leqslant k \leqslant 5000$).

### Output

Output the sum of costs for all non-empty subsets modulo $10^9+7$.

### Hint

There are seven non-empty subsets.

• $\{1\}$ with cost $1^2 = 1$
• $\{2\}$ with cost $1^2 = 1$
• $\{1, 2\}$ with cost $2^2 = 4$
• $\{3\}$ with cost $1^2 = 1$
• $\{1, 3\}$ with cost $2^2 = 4$
• $\{2, 3\}$ with cost $2^2 = 4$
• $\{1, 2, 3\}$ with cost $3^2 = 9$

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.

## Solution

$dp(j, i)$ 表示由不同的 $i$ 个人构成的大小为 $j$ 的组合的方案数，那么答案为

$\displaystyle \sum_{i=1}^{\min \{n, k\}} \Big(dp(k, i) \cdot 2^{n-i}\Big)$

$dp(j, i)$ 可以很容易用动态规划求出，即

$dp(j, i) = i \cdot dp(j-1, i) + (n-i+1) \cdot dp(j-1, i-1)$