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 long long Mod = 1e9 + 7;
long long add(long long a, const long long b) {
  a += b;
  if (a >= Mod) a -= Mod;
  return a;
}
long long sub(long long a, const long long b) {
  a -= b;
  if (a < 0) a += Mod;
  return a;
}
long long mul(const long long a, const long long b) {
  return (long long)a * b % Mod;
}
long long power(long long x, long long cs) {
  long long ras = 1;
  while (cs) {
    if (cs & 1) ras = mul(ras, x);
    x = mul(x, x);
    cs >>= 1;
  }
  return ras;
}
const double PI = acos(-1);
const long long L = (1 << 14), N = L + 20, S = (1 << 16) - 1;
long long lo[N], rev[N];
complex<double> g[2][N];
void init() {
  long long i;
  double sita;
  for (i = 2; i <= L; i++) lo[i] = lo[i >> 1] + 1;
  for (i = 0; i < L; i++) {
    sita = 2.0 * PI * i / L;
    g[0][i] = complex<double>(cos(sita), sin(sita));
    g[1][i] = complex<double>(cos(-sita), sin(-sita));
  }
}
void DFT(long long n, long long opt, complex<double> *w) {
  long long i, j, mws, len, mid;
  complex<double> tmp;
  mws = lo[n] - 1;
  for (i = 1; i < n; i++) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << mws);
  }
  for (i = 1; i < n; i++) {
    if (rev[i] < i) swap(w[rev[i]], w[i]);
  }
  for (len = 2; len <= n; len <<= 1) {
    mid = len >> 1;
    for (i = 0; i < n; i += len) {
      for (j = 0; j < mid; j++) {
        tmp = g[opt][L / len * j] * w[i + mid + j];
        w[i + mid + j] = w[i + j] - tmp;
        w[i + j] = w[i + j] + tmp;
      }
    }
  }
}
void trans(long long n, long long *a, long long *b, long long *c) {
  long long i, len;
  static complex<double> h1[N], h2[N];
  for (len = 1; len < n * 2; len <<= 1)
    ;
  memset(h1, 0, sizeof(h1));
  memset(h2, 0, sizeof(h2));
  for (i = 0; i < n; i++) {
    h1[i].real(a[i]);
    h2[i].real(b[i]);
  }
  DFT(len, 0, h1);
  DFT(len, 0, h2);
  for (i = 0; i < len; i++) h1[i] *= h2[i];
  DFT(len, 1, h1);
  for (i = 0; i < n * 2; i++) {
    h1[i] /= len;
    c[i] = floor(h1[i].real() + 0.5);
  }
}
void strans(long long n, long long *a, long long *b, long long *c) {
  long long i, len;
  static long long a1[N], a2[N], b1[N], b2[N], h[N];
  for (len = 1; len < n * 2; len <<= 1)
    ;
  memset(a1, 0, sizeof(a1));
  memset(a2, 0, sizeof(a2));
  memset(b1, 0, sizeof(b1));
  memset(b2, 0, sizeof(b2));
  for (i = 0; i < n; i++) {
    a1[i] = a[i] >> 16;
    a2[i] = a[i] & S;
    b1[i] = b[i] >> 16;
    b2[i] = b[i] & S;
  }
  for (i = 0; i < n * 2; i++) c[i] = 0;
  trans(n, a1, b1, h);
  for (i = 0; i < n * 2; i++)
    c[i] = add(c[i], mul(h[i] % Mod, (1ll << 32) % Mod));
  trans(n, a1, b2, h);
  for (i = 0; i < n * 2; i++) c[i] = add(c[i], mul(h[i] % Mod, 1 << 16));
  trans(n, a2, b1, h);
  for (i = 0; i < n * 2; i++) c[i] = add(c[i], mul(h[i] % Mod, 1 << 16));
  trans(n, a2, b2, h);
  for (i = 0; i < n * 2; i++) c[i] = add(c[i], h[i] % Mod);
}
const long long Log = 29;
long long n, K;
long long f[Log + 3][N], h[N], zp[N], fp[N];
void trans(long long *a, long long *b, long long *c) {
  long long i, j, tmp;
  for (i = K; i >= 0; i--) {
    tmp = 0;
    for (j = 0; j <= i; j++) tmp = add(tmp, mul(a[j], b[i - j]));
    c[i] = tmp;
  }
}
int main() {
  init();
  long long i;
  cin >> n >> K;
  zp[0] = fp[0] = 1;
  for (i = 1; i <= K; i++) zp[i] = mul(zp[i - 1], i);
  fp[K] = power(zp[K], Mod - 2);
  for (i = K - 1; i >= 1; i--) fp[i] = mul(fp[i + 1], i + 1);
  for (i = 1; i <= K; i++) f[0][i] = fp[i];
  f[0][0] = 2;
  for (i = 1; i <= Log; i++) strans(K + 1, f[i - 1], f[i - 1], f[i]);
  h[0] = 1;
  for (i = Log; i >= 0; i--) {
    if (n & (1 << i)) strans(K + 1, h, f[i], h);
  }
  printf("%lld\n", mul(h[K], zp[K]));
  return 0;
}