Problem: 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 xk. 

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

Input

Only line of input contains two integers N (1 ≤ N ≤ 109) 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 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.

Solution (in PYTHON3):

Solution:
# ############################## import
# def stirling2_list(n, mod=10 ** 9 + 7):
#     if not n:
#         return [0]
#     res = [0, 1]
#     for i in range(n - 1):
#         res = [0, 1] + [(res[j - 1] + j * res[j]) % mod for j in range(2, 2 + i)] + [1]
#     return res

# Explain:
# ans = \sum_{i=1}^{n} \binom{n}{i} i^k
# Notice that (1+x)^n = \sum_{i=0}^{n} \binom{n}{i} x^i
# differential and multiply by x on both side, we can get
# n(1+x)^{n-1}x=\sum_{i=0}^{n}\binom{n}{i}ix^i
# we can keep doing this process to get \sum_{i=0}^{n}\binom{n}{i}i^kx^i
# and the answer is the left side function, with x = 1
#
# Let f_0(x) = (1+x)^n
# and f_m(x) = f_{m-1}'(x)x
# so the answer is f_{k}(1)
# We calculate the first few of patterns
# We can observe that:
# f_1 = f_0'x
# f_2 = f_0'x + 1f_0''x^2
# f_3 = f_0'x + 3f_0''x^2 + f_0'''x^3
# f_4 = f_0'x + 7f_0''x^2 + 6f_0'''x^3 + f_0''''x^4
# The coefficients is Stirling numbers of the second kind
# And f_0 with differentiating k times is just
# n(n-1)(n-2)...(n-(k-1))(1+x)^{n-k}
# We can find them out in one iteration
# ############################## main

MOD = 10 ** 9 + 7
INV = 500000004
n, k = map(int, input().split())
# (1+x)^n, n(1+x)^{n-1}, n(n-1)(1+x)^{n-2}, ...
# 2^n,  n*2^{n-1}, n(n-1)*2^{n-2}, ...
# f_4 = f_0' + 7f_0'' + 6f_0''' + f_0''''
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)