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;
template <typename T>
inline void read(T &t) {
  T f = 1;
  char ch = getchar();
  t = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -f;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') t = t * 10 + ch - '0', ch = getchar();
  t *= f;
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
const long long p = 1e9 + 7;
inline long long power(register long long x, register long long k = p - 2) {
  register long long re = 1;
  for (; k; k >>= 1, x = x * x % p)
    if (k & 1) re = re * x % p;
  return re;
}
const long double PI = acos(-1.0);
struct Complex {
  long double real, fake;
  Complex(long double A, long double B) {
    real = A;
    fake = B;
  }
  Complex() { real = fake = 0; }
  Complex operator+(Complex B) { return Complex(real + B.real, fake + B.fake); }
  Complex operator-(Complex B) { return Complex(real - B.real, fake - B.fake); }
  Complex operator*(Complex B) {
    return Complex(real * B.real - fake * B.fake,
                   real * B.fake + fake * B.real);
  }
};
int rev[400005];
void FFT(Complex *f, int lim, int flag) {
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int len = 1; len < lim; len <<= 1) {
    Complex wn(cos(PI / len), sin(PI / len));
    if (flag != 1) wn.fake *= -1;
    for (int l = 0; l < lim; l += len << 1) {
      Complex buf(1, 0), tp;
      for (int i = l; i < l + len; i++) {
        tp = f[i + len] * buf;
        f[i + len] = f[i] - tp;
        f[i] = f[i] + tp;
        buf = buf * wn;
      }
    }
  }
  if (flag == 1) return;
  for (int i = 0; i < lim; i++) f[i].real = (f[i].real / lim + 0.49);
}
void MUL(long long *f, long long *g, long long *ans, int n, int m) {
  static Complex _f[2][400005], _g[2][400005], h[3][400005];
  static int _n, _m;
  _n = n;
  _m = m;
  m += n;
  n = 1;
  while (n < m) n <<= 1;
  for (int i = 0; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
  for (int i = 0; i < _n; i++)
    _f[0][i].real = f[i] & 32767, _f[1][i].real = f[i] >> 15;
  for (int i = 0; i < _m; i++)
    _g[0][i].real = g[i] & 32767, _g[1][i].real = g[i] >> 15;
  FFT(_f[0], n, 1);
  FFT(_f[1], n, 1);
  FFT(_g[0], n, 1);
  FFT(_g[1], n, 1);
  for (int i = 0; i < n; i++) {
    h[0][i] = _f[0][i] * _g[0][i];
    h[1][i] = _f[1][i] * _g[0][i] + _f[0][i] * _g[1][i];
    h[2][i] = _f[1][i] * _g[1][i];
  }
  FFT(h[0], n, 0);
  FFT(h[1], n, 0);
  FFT(h[2], n, 0);
  for (int i = 0; i < m; i++)
    ans[i] =
        ((long long)h[0][i].real + ((long long)h[1][i].real % p << 15) % p +
         ((long long)h[2][i].real % p << 30) % p) %
        p;
}
int n, k;
long long fac[800005];
long long f[800005], g[800005], h[800005];
int main() {
  read(n, k);
  fac[0] = 1;
  for (int i = 1; i <= k; i++) fac[i] = fac[i - 1] * i % p;
  for (int i = 0; i <= k; i++)
    f[i] = (i & 1 ? p - 1 : 1) * power(fac[i], p - 2) % p;
  for (int i = 0; i <= k; i++) g[i] = power(i, k) * power(fac[i], p - 2) % p;
  MUL(f, g, h, k + 1, k + 1);
  long long ans = 0, BC = n;
  for (int i = 1; i <= min(n, k); i++) {
    ans = (ans + h[i] * BC % p * power(2, n - i) % p) % p;
    BC = BC * (n - i) % p;
  }
  printf("%lld\n", ans);
  return 0;
}