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.
#include <bits/stdc++.h>
using namespace std;
void codeforces_463_A() {
  char c[1001];
  scanf("%s", c);
  for (int i = 0; i < strlen(c); i++) {
    printf("%c", c[i]);
  }
  for (int i = 0; i < strlen(c); i++) {
    printf("%c", c[strlen(c) - 1 - i]);
  }
}
void codeforces_463_B() {
  int n;
  cin >> n;
  int b[1000001];
  int a[10][1000001];
  for (int j = 1; j < 10; j++) {
    a[j][0] = 0;
  }
  for (int i = 1; i < 10; i++) {
    for (int j = 1; j < i; j++) {
      a[i][j] = 0;
    }
    for (int j = i; j < 10; j++) {
      a[i][j] = 1;
    }
    b[i] = i;
  }
  for (int i = 10; i <= 1000000; i++) {
    int b1 = 0;
    int b2 = 0;
    int b3 = 0;
    int b4 = 0;
    int b5 = 0;
    int b6 = 0;
    int b7 = 0;
    b1 = i % 10;
    b2 = (i % 100) / 10;
    b3 = (i % 1000) / 100;
    b4 = (i % 10000) / 1000;
    b5 = (i % 100000) / 10000;
    b6 = (i % 1000000) / 100000;
    b7 = (i % 10000000) / 1000000;
    if (b1 == 0) {
      b1 = 1;
    }
    if (b2 == 0) {
      b2 = 1;
    }
    if (b3 == 0) {
      b3 = 1;
    }
    if (b4 == 0) {
      b4 = 1;
    }
    if (b5 == 0) {
      b5 = 1;
    }
    if (b6 == 0) {
      b6 = 1;
    }
    if (b7 == 0) {
      b7 = 1;
    }
    b[i] = b[b1 * b2 * b3 * b4 * b5 * b6 * b7];
    for (int k = 1; k < 10; k++) {
      a[k][i] = a[k][i - 1];
    }
    a[b[i]][i]++;
  }
  for (int i = 0; i < n; i++) {
    int l, r, k;
    cin >> l;
    cin >> r;
    cin >> k;
    printf("%d\n", a[k][r] - a[k][l - 1]);
  }
}
void codeforces_463_C() {
  int n, a, b;
  cin >> n;
  cin >> a;
  cin >> b;
  int iii = -1;
  int jjj = 0;
  for (int i = 0; i <= n / a; i++) {
    if ((n - i * a + b) % b == 0) {
      iii = i;
      jjj = (n - i * a) / b;
    }
  }
  if (iii == -1) {
    printf("-1");
    return;
  } else {
    if (a == 1) {
      for (int i = 0; i < iii * a; i++) {
        printf("%d ", i + 1);
      }
    } else {
      for (int i = 0; i < iii * a; i++) {
        if ((i + 1) % a != 0) {
          printf("%d ", i + 2);
        } else {
          printf("%d ", i - a + 2);
        }
      }
    }
    if (b == 1) {
      for (int j = iii * a; j < n; j++) {
        printf("%d ", j + 1);
      }
    } else {
      for (int j = 0; j < n - iii * a; j++) {
        if ((j + 1) % b != 0) {
          printf("%d ", j + 2 + iii * a);
        } else {
          printf("%d ", j + 2 - b + iii * a);
        }
      }
    }
  }
}
void codeforces_463_D() {}
int power(int a, unsigned int b) {
  if (b == 0) {
    return 1;
  }
  int p;
  p = power(a, b / 2) % (1000000007);
  p = ((long long)p * (long long)p) % (1000000007);
  return (b % 2 == 0) ? (long long)p
                      : ((long long)a * (long long)p) % 1000000007;
}
void codeforces_463_E() {
  int n, k;
  cin >> n;
  cin >> k;
  int B[k + 1];
  int S[k + 1][k + 1];
  for (int i = 0; i <= k; i++) {
    S[i][0] = 0;
  }
  S[0][0] = 1;
  for (int i = 0; i <= k; i++) {
    for (int j = i + 1; j <= k; j++) {
      S[i][j] = 0;
    }
  }
  for (int i = 1; i <= k; i++) {
    for (int j = 1; j <= i; j++) {
      S[i][j] = ((long long)j * (long long)(S[i - 1][j]) +
                 (long long)(S[i - 1][j - 1])) %
                1000000007;
    }
  }
  B[0] = power(2, (unsigned int)n);
  for (int i = 1; i <= k; i++) {
    if (B[i - 1] % 2 == 0) {
      B[i] = B[i - 1] / 2;
    } else {
      B[i] = ((long long)(B[i - 1]) + 1000000007) / 2;
    }
    B[i] = ((long long)(B[i]) * ((long long)n - i + 1)) % 1000000007;
  }
  int ans = 0;
  for (int i = 0; i <= k; i++) {
    ans = ((long long)ans + (long long)B[i] * (long long)S[k][i]) % 1000000007;
  }
  printf("%d", ans);
}
void codeforces_463_F() {}
void codeforces_463_G() {}
int main() {
  codeforces_463_E();
  return 0;
}
