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 unsigned int Max_K = 5005;
const unsigned int Mod = 1000000007;
unsigned long long int Power(unsigned long long int Base, unsigned int Exp) {
  unsigned long long int res = 1;
  for (; Exp; Base = Base * Base % Mod, Exp >>= 1)
    if (Exp & 1) res = res * Base % Mod;
  return res;
}
unsigned int N, K;
unsigned int Pcnt, Prime[Max_K];
bool is_comp[Max_K];
unsigned int Kth_Power[Max_K], Inv[Max_K], BinomialF[Max_K], BinomialR[Max_K];
int main(int argc, char **argv) {
  scanf("%u %u", &N, &K);
  Kth_Power[0U] = K == 0, BinomialF[0U] = 1U, BinomialR[0U] = 1U;
  Kth_Power[1U] = 1U, Inv[1U] = 1U, BinomialF[1U] = N, BinomialR[1U] = N - K;
  for (unsigned int i = 2U; i <= K; ++i) {
    if (!is_comp[i]) {
      Prime[Pcnt++] = i;
      Kth_Power[i] = Power(i, K);
      Inv[i] = static_cast<unsigned long long int>(Mod - Mod / i) *
               Inv[Mod % i] % Mod;
    }
    for (unsigned int j = 0U; j != Pcnt && i * Prime[j] <= K; ++j) {
      is_comp[i * Prime[j]] = true;
      Kth_Power[i * Prime[j]] =
          static_cast<unsigned long long int>(Kth_Power[i]) *
          Kth_Power[Prime[j]] % Mod;
      Inv[i * Prime[j]] =
          static_cast<unsigned long long int>(Inv[i]) * Inv[Prime[j]] % Mod;
      if (i % Prime[j] == 0U) break;
    }
    BinomialF[i] = BinomialF[i - 1] * (N - i + 1ULL) % Mod * Inv[i] % Mod;
    BinomialR[i] = BinomialR[i - 1] * (N - K - 1ULL + i) % Mod * Inv[i] % Mod;
  }
  unsigned int Ans = 0U;
  if (N <= K) {
    for (unsigned int i = 0U; i <= N; ++i)
      Ans = (Ans +
             static_cast<unsigned long long int>(BinomialF[i]) * Kth_Power[i]) %
            Mod;
  } else {
    unsigned int coef = 1U, sbinom = 0U;
    for (unsigned int i = 0U; i <= K; ++i)
      sbinom =
          (sbinom + BinomialF[i] * static_cast<unsigned long long int>(coef)) %
          Mod,
      coef = coef * ((Mod - 1ULL) / 2U) % Mod;
    unsigned int Power2 = Power(2U, N);
    for (unsigned int i = 0U; i <= K; ++i) {
      Ans = (Ans + static_cast<unsigned long long int>(BinomialF[i]) *
                       Kth_Power[i] % Mod * Power2 % Mod * sbinom) %
            Mod;
      coef = coef * (Mod - 2ULL) % Mod;
      sbinom =
          (sbinom + Mod -
           static_cast<unsigned long long int>(coef) * BinomialR[K - i] % Mod) *
          2U % Mod;
      Power2 = Power2 * ((Mod + 1ULL) / 2U) % Mod;
    }
  }
  printf("%u", Ans);
  return 0;
}