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 10^9 + 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.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
(n, k) = map(int, input().split())
m = int(1000000000.0 + 7)
r = 0
p = pow(2, n, m)
a = [1] + [0] * k
for i in range(k):
	for j in range(i, -1, -1):
		a[j + 1] += a[j]
		a[j] = a[j] * j % m
for i in range(k + 1):
	r += p * a[i]
	p = p * 500000004 * (n - i) % m
print(r % m)


MOD = 10 ** 9 + 7
INV = 500000004
(n, k) = map(int, input().split())
d = 1
p = pow(2, n, MOD)
ans = 0
stirling2_list = [0, 1]
for i in range(k - 1):
	stirling2_list = [0, 1] + [(stirling2_list[j - 1] + j * stirling2_list[j]) % MOD for j in range(2, 2 + i)] + [1]
for stirling in stirling2_list:
	ans = (ans + stirling * d * p) % MOD
	d = d * n % MOD
	n -= 1
	p = p * INV % MOD
print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
(N, k) = MI()
mod = 10 ** 9 + 7
inv_2 = (mod + 1) // 2
x = pow(2, N, mod)
X = [0] * (k + 1)
for i in range(k + 1):
	X[i] = x
	x *= (N - i) * inv_2
	x %= mod
coefficient = [0] * (k + 1)
coefficient[0] = 1
for _ in range(k):
	for j in range(k, -1, -1):
		coefficient[j] = coefficient[j] * j + coefficient[j - 1]
		coefficient[j] %= mod
ans = 0
for i in range(1, k + 1):
	ans += coefficient[i] * X[i]
	ans %= mod
print(ans)


(n, k) = map(int, input().split())
dp = [0 for i in range(k + 1)]
mod = 10 ** 9 + 7
dp[0] = 1
for i in range(k):
	for j in range(1, k + 1)[::-1]:
		dp[j] = (dp[j] * j + dp[j - 1] * (n - j + 1)) % mod
	dp[0] = 0
ans = 0
for i in range(k + 1):
	if n < i:
		continue
	ans += dp[i] * pow(2, n - i, mod)
	ans %= mod
print(ans)


(n, k) = list(map(int, input().split()))
m = 1000000007
v = 500000004
r = 0
p = pow(2, n, m)
a = [1] + [0] * k
for i in range(k):
	for j in range(i, -1, -1):
		a[j + 1] += a[j]
		a[j] = a[j] * j % m
for i in range(k + 1):
	r = (r + p * a[i]) % m
	p = p * v * (n - i) % m
print(r)