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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int ksm(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = 1ll * a * a % 1000000007)
    if (b & 1) s = 1ll * s * a % 1000000007;
  return s;
}
int add(int a, int b) {
  a += b;
  return a >= 1000000007 ? a - 1000000007 : a;
}
void Inc(int &a, int b) { a = add(a, b); }
void PolyGet(int n, int *x, int *y, int *res) {
  static int P[5005], inv[5005], tmp[5005];
  memset(P, 0, sizeof(P));
  memset(tmp, 0, sizeof(tmp));
  for (int i = 1; i <= n; i++) inv[i] = ksm(x[i], 1000000007 - 2);
  P[0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = n; j >= 0; j--)
      P[j] = add(1ll * P[j] * (1000000007 - x[i]) % 1000000007, P[j - 1]);
  for (int i = 1; i <= n; i++) {
    tmp[0] = 1ll * P[0] * inv[i] % 1000000007, tmp[0] = 1000000007 - tmp[0];
    int div = 1;
    for (int j = 1; j <= n; j++)
      if (i != j) div = 1ll * div * add(x[i], 1000000007 - x[j]) % 1000000007;
    for (int j = 1; j <= n - 1; j++)
      tmp[j] = 1ll * add(tmp[j - 1], 1000000007 - P[j]) * inv[i] % 1000000007;
    div = ksm(div, 1000000007 - 2);
    for (int j = 0; j <= n - 1; j++)
      Inc(res[j], 1ll * tmp[j] * y[i] % 1000000007 * div % 1000000007);
  }
}
int A[5005], B[5005], poly[5005];
int C[5005][5005];
int n, k;
void Pre() {
  for (int i = 0; i < 5005; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
  }
}
int pw[5005];
int main() {
  Pre();
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k + 1; i++) pw[i] = ksm(i, k);
  for (int i = 1; i <= k + 1; i++) {
    B[i] = i;
    for (int j = 1; j <= i; j++) Inc(A[i], 1ll * C[i][j] * pw[j] % 1000000007);
    A[i] = 1ll * A[i] *
           (i < k ? ksm(2, k - i) : ksm(ksm(2, i - k), 1000000007 - 2)) %
           1000000007;
  }
  PolyGet(k + 1, B, A, poly);
  int ans = 0;
  for (int i = 0, nw = 1; i <= k; i++) {
    Inc(ans, 1ll * poly[i] * nw % 1000000007);
    nw = 1ll * nw * n % 1000000007;
  }
  printf("%d\n",
         1ll * ans *
             (n < k ? ksm(ksm(2, k - n), 1000000007 - 2) : ksm(2, n - k)) %
             1000000007);
  return 0;
}