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>
const long long N = 5e3 + 5, mod = 1e9 + 7;
using namespace std;
long long read() {
  long long x = 0, f = 1;
  char ch;
  while (!isdigit(ch = getchar())) (ch == '-') && (f = -f);
  for (x = ch ^ 48; isdigit(ch = getchar());
       x = (x << 3) + (x << 1) + (ch ^ 48))
    ;
  return x * f;
}
template <class T>
T Max(T a, T b) {
  return a > b ? a : b;
}
template <class T>
T Min(T a, T b) {
  return a < b ? a : b;
}
long long n, k, ans, Pow, inv2, S[N][N];
long long ksm(long long x, long long y) {
  long long res = 1;
  for (; y; x = x * x % mod, y >>= 1) {
    if (y & 1) res = res * x % mod;
  }
  return res;
}
void init() {
  S[0][0] = 1;
  for (long long i = 1; i <= k; ++i) {
    for (long long j = 1; j <= i; ++j)
      S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j) % mod;
  }
}
signed main() {
  n = read();
  k = read();
  init();
  Pow = ksm(2, n);
  inv2 = ksm(2, mod - 2);
  for (long long i = 0, tmp = 1; i <= k; ++i) {
    ans = (ans + Pow * tmp % mod * S[k][i] % mod) % mod;
    Pow = Pow * inv2 % mod;
    tmp = tmp * (n - i) % mod;
  }
  printf("%lld\n", ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}