『Codeforces 932E』Team Work

Problem

time limit per test

2 seconds

memory limit per test

256 megabytes

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

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

Output

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

Examples

input

1 1

output

1

input

3 2

output

24

Note

In the first example, there is only one non-empty subset $\{1\}$ with cost $1^1 = 1$

In the second example, 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

这题还是挺难的…稍不注意就会掉到什么二项式反演的坑里面去…（其实还是做题少

正解是什么呢？

设函数$\displaystyle f(x)=(1+x)^n=\sum_{r=0}^nC_n^rx^r$

两边形式地求导：$\displaystyle f’(x)=n(1+x)^{n-1}=\sum_{r=1}^nC_n^rrx^{r-1}$

再两边乘$x$：$\displaystyle xf’(x)=nx(1+x)^{n-1}=\sum_{r=1}^nC_n^rrx^{r}$

然后你发现了什么？
请思考 for some time

对于$f(x)$，题目所给的公式就是我们对它进行上面的操作（求导后乘$x$）$k$次后$x=1$的值！

那么这道题现在就转化成关于$f(x)$的问题了

设$f_{a,b,c}$是对$x^b(1+x)^c$做$a$次操作后$x=1$的值

那么最终的答案即为$f_{k,0,n}$

转移：$f_{a,b,c}=b∗f_{a-1,b,c}+c∗f_{a-1,b+1,c-1}$

$a=0$时,$f_{a,b,c}=2^c$

复杂度实际上是$O(k^2)$，因为$b+c≡n$

这题目的long long一定不能忘了开！！！（栽坑

Code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 5000 + 10;
ll f[MAXN][MAXN];
ll n, k;
const ll mod = 1e9 + 7;
inline ll fast_pow(ll x, ll a)
{
	register ll ans = 1;
	for (; a; a >>= 1, x = 1ll * x * x % mod) if (a & 1) ans = 1ll * ans * x % mod;
	return ans;
}
inline ll dp(const ll &a, const ll &b)
{
	if (b > n) return 0;
	if (f[a][b] >= 0) return f[a][b];
	register ll c = n - b;
	if (!a) { f[a][b] = fast_pow(2, c); return f[a][b]; }
	f[a][b] = (1ll * b * dp(a - 1, b) + 1ll * c * dp(a - 1, b + 1)) % mod;
	return f[a][b];
}
inline void _read(ll &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}
int main()
{
	_read(n), _read(k);
	memset(f, -1, sizeof f);
	printf("%lld", dp(k, 0));
}