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;
const double eps = 1e-7;
const int INF = 0x7f7f7f7f;
const long long mo = 1e9 + 7;
template <typename _T>
_T Fabs(_T x) {
  return x < 0 ? -x : x;
}
template <typename _T>
void read(_T &x) {
  _T f = 1;
  x = 0;
  char s = getchar();
  while (s > '9' || s < '0') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while ('0' <= s && s <= '9') {
    x = (x << 3) + (x << 1) + (s ^ 48);
    s = getchar();
  }
  x *= f;
}
int qkpow(int a, int s) {
  int t = 1;
  while (s) {
    if (s & 1) t = 1ll * a * t % mo;
    a = 1ll * a * a % mo;
    s >>= 1;
  }
  return t;
}
int add(int x, int y) { return x + y >= mo ? x + y - mo : x + y; }
int n, k, f[5005], c[5005], inv[5005], pw[5005], prime[5005], cntp;
void init() {
  c[0] = inv[1] = pw[1] = 1;
  c[1] = n;
  for (int i = 2; i <= k + 1; i++) {
    inv[i] = 1ll * (mo - mo / i) * inv[mo % i] % mo;
    c[i] = 1ll * c[i - 1] * inv[i] % mo * (n - i + 1) % mo;
    if (!pw[i]) prime[++cntp] = i, pw[i] = qkpow(i, k);
    for (int j = 1; j <= cntp && i * prime[j] <= k; j++) {
      pw[i * prime[j]] = 1ll * pw[i] * pw[prime[j]] % mo;
      if (i % prime[j] == 0) break;
    }
  }
}
int work1() {
  int res = 0;
  for (int i = 1; i <= n; i++) res = add(res, 1ll * c[i] * pw[i] % mo);
  return res;
}
int work2() {
  int mul, c2, res = 0;
  mul = c2 = f[k] = 1;
  for (int i = k - 1; i > 0; i--) {
    c2 = 1ll * c2 * (n - i - 1) % mo * inv[k - i] % mo;
    mul = 1ll * mul * (mo - inv[2]) % mo;
    f[i] = add(1ll * c2 * mul % mo, 1ll * inv[2] * f[i + 1] % mo);
  }
  mul = inv[2];
  for (int i = 1; i <= k; i++) {
    res = add(res, 1ll * pw[i] * c[i] % mo * mul % mo * f[i] % mo);
    mul = 1ll * mul * inv[2] % mo;
  }
  res = 1ll * res * qkpow(2, n) % mo;
  return res;
}
signed main() {
  read(n);
  read(k);
  init();
  if (n <= k + 1)
    printf("%d\n", work1());
  else
    printf("%d\n", work2());
  return 0;
}