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;
long long const N = 5e3 + 15;
long long INF = 0x3f3f3f3f;
long long const mod = 1000000007;
long long x[N], y[N], ik[N];
long long c[N][N], f[N];
long long qpow(long long a, long long b) {
  long long s = 1;
  while (b) {
    if (b & 1) {
      s *= a;
      s %= mod;
    }
    b /= 2;
    a *= a;
    a %= mod;
  }
  return s;
}
long long inv(long long a) { return qpow(a, mod - 2); }
void dabiao() {
  c[0][0] = 1;
  long long ln = 5005;
  for (int i = 1; i <= ln; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
      c[i][j] %= mod;
    }
  }
}
int main() {
  dabiao();
  long long n, k;
  cin >> n >> k;
  for (int i = 1; i <= 5003; i++) {
    ik[i] = qpow(i, k);
    ik[i] %= mod;
  }
  f[0] = 1;
  for (int i = 1; i <= 5005; i++) {
    f[i] = f[i - 1] * i;
    f[i] %= mod;
  }
  long long s = 0;
  for (int nn = 1; nn <= 5003; nn++) {
    s = 0;
    for (int i = 1; i <= nn; i++) {
      long long nv = c[nn][i];
      s += ik[i] * nv;
      if (s > mod) s %= mod;
    }
    y[nn] = s;
    if (nn < k) {
      y[nn] *= qpow(2, k - nn);
    } else {
      y[nn] *= qpow(qpow(2, nn - k), mod - 2);
    }
    y[nn] %= mod;
  }
  y[0] = 0;
  if (n <= k + 3) {
    if (n >= k) {
      y[n] *= qpow(2, n - k);
      y[n] %= mod;
    } else {
      y[n] *= inv(qpow(2, k - n));
      y[n] %= mod;
    }
    cout << y[n] << endl;
    return 0;
  }
  for (int i = 0; i <= 5005; i++) {
    x[i] = i;
  }
  long long td = 1;
  for (int i = 1; i <= k + 1; i++) {
    td *= (n - x[i]);
    td %= mod;
  }
  s = 0;
  for (int i = 1; i <= k + 1; i++) {
    long long ans = 1, an = 1;
    an = f[i - 1] * f[k + 1 - i];
    an %= mod;
    if ((k + 1 - i) % 2 == 1) an *= -1;
    an += mod;
    an %= mod;
    an *= (n - x[i]);
    an %= mod;
    ans = td;
    ans *= qpow(an, mod - 2);
    ans %= mod;
    ans *= y[i];
    ans %= mod;
    s += ans;
    s %= mod;
  }
  s += mod;
  s %= mod;
  s %= mod;
  s += mod;
  s %= mod;
  s *= qpow(2, n - k);
  s %= mod;
  cout << s << endl;
  return 0;
}