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, typename U>
T power(T n, U x) {
  assert(x >= 0);
  T res = 1;
  for (; x; x /= 2, n *= n)
    if (x & 1) res *= n;
  return res;
}
template <typename T>
T inverse(T a, T m) {
  T x = 0, y = 1;
  while (a != 0) {
    T q = m / a;
    m -= q * a;
    swap(a, m);
    x -= q * y;
    swap(x, y);
  }
  assert(m == 1);
  return x;
}
template <typename T>
class Modular {
 private:
  using Type = typename decay<decltype(T::value)>::type;
  Type value;

 public:
  Modular() { value = 0; }
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  Type normalize(const U& x) {
    Type res;
    if (-mod() <= x && x < mod()) {
      res = static_cast<Type>(x);
    } else {
      res = static_cast<Type>(x % mod());
    }
    if (res < 0) {
      res += mod();
    }
    return res;
  }
  explicit operator Type() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& o) {
    if ((value += o.value) >= mod()) value -= mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& o) {
    return *this += Modular(o);
  }
  Modular& operator-=(const Modular& o) {
    if ((value -= o.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator-=(const U& o) {
    return *this -= Modular(o);
  }
  Modular& operator*=(const Modular& o) {
    value = normalize(1ll * value * o.value);
    return *this;
  }
  template <typename U>
  Modular& operator*=(const U& o) {
    return *this *= Modular(o);
  }
  Modular& operator/=(const Modular& o) {
    return *this *= Modular(inverse(o.value, mod()));
  }
  template <typename U>
  Modular& operator/=(const U& o) {
    return *this /= Modular(o);
  }
  Modular operator+() { return Modular(+value); }
  Modular operator-() { return Modular(-value); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  friend ostream& operator<<(ostream& os, const Modular& x) {
    os << x.value;
    return os;
  }
  friend istream& operator>>(istream& is, Modular& x) {
    typename common_type<Type, int64_t>::type in;
    is >> in;
    x.value = x.normalize(in);
    return is;
  }
  friend bool operator==(const Modular& a, const Modular& b) {
    return a.value == b.value;
  }
  template <typename U>
  friend bool operator==(const Modular& a, U b) {
    return a == Modular(b);
  }
  template <typename U>
  friend bool operator==(U a, const Modular& b) {
    return Modular(a) == b;
  }
  friend bool operator!=(const Modular& a, const Modular& b) {
    return a.value != b.value;
  }
  template <typename U>
  friend bool operator!=(const Modular& a, U b) {
    return a != Modular(b);
  }
  template <typename U>
  friend bool operator!=(U a, const Modular& b) {
    return Modular(a) != b;
  }
  friend bool operator>(const Modular& a, const Modular& b) {
    return a.value > b.value;
  }
  template <typename U>
  friend bool operator>(const Modular& a, U b) {
    return a > Modular(b);
  }
  template <typename U>
  friend bool operator>(U a, const Modular& b) {
    return Modular(a) > b;
  }
  friend bool operator<(const Modular& a, const Modular& b) {
    return a.value < b.value;
  }
  template <typename U>
  friend bool operator<(const Modular& a, U b) {
    return a < Modular(b);
  }
  template <typename U>
  friend bool operator<(U a, const Modular& b) {
    return Modular(a) < b;
  }
  friend bool operator>=(const Modular& a, const Modular& b) {
    return a.value >= b.value;
  }
  template <typename U>
  friend bool operator>=(const Modular& a, U b) {
    return a >= Modular(b);
  }
  template <typename U>
  friend bool operator>=(U a, const Modular& b) {
    return Modular(a) <= b;
  }
  friend bool operator<=(const Modular& a, const Modular& b) {
    return a.value <= b.value;
  }
  template <typename U>
  friend bool operator<=(const Modular& a, U b) {
    return a <= Modular(b);
  }
  template <typename U>
  friend bool operator<=(U a, const Modular& b) {
    return Modular(a) <= b;
  }
  friend Modular operator+(const Modular& a, const Modular& b) {
    return Modular(a) += b;
  }
  template <typename U>
  friend Modular operator+(const Modular& a, const U& b) {
    return Modular(a) += Modular(b);
  }
  template <typename U>
  friend Modular operator+(const U& a, const Modular& b) {
    return Modular(a) += b;
  }
  friend Modular operator-(const Modular& a, const Modular& b) {
    return Modular(a) -= b;
  }
  template <typename U>
  friend Modular operator-(const Modular& a, const U& b) {
    return Modular(a) -= Modular(b);
  }
  template <typename U>
  friend Modular operator-(const U& a, const Modular& b) {
    return Modular(a) -= b;
  }
  friend Modular operator*(const Modular& a, const Modular& b) {
    return Modular(a) *= b;
  }
  template <typename U>
  friend Modular operator*(const Modular& a, const U& b) {
    return Modular(a) *= Modular(b);
  }
  template <typename U>
  friend Modular operator*(const U& a, const Modular& b) {
    return Modular(a) *= b;
  }
  friend Modular operator/(const Modular& a, const Modular& b) {
    return Modular(a) /= b;
  }
  template <typename U>
  friend Modular operator/(const Modular& a, const U& b) {
    return Modular(a) /= Modular(b);
  }
  template <typename U>
  friend Modular operator/(const U& a, const Modular& b) {
    return Modular(a) /= b;
  }
};
constexpr int MOD = 1e9 + 7;
using Mint = Modular<integral_constant<decay<decltype(MOD)>::type, MOD>>;
int main() {
  int N, K;
  cin >> N >> K;
  vector<vector<Mint>> DP(K + 2, vector<Mint>(K + 2, 0));
  DP[0][0] = 1;
  for (int tuple = 0; tuple <= K; tuple++) {
    for (int distinct = 0; distinct <= tuple; distinct++) {
      DP[tuple + 1][distinct] += distinct * DP[tuple][distinct];
      DP[tuple + 1][distinct + 1] += (N - distinct) * DP[tuple][distinct];
    }
  }
  Mint ans = 0;
  for (int distinct = 1; distinct <= K; distinct++) {
    ans += DP[K][distinct] / power((Mint)2, distinct);
  }
  ans *= power((Mint)2, N);
  cout << ans << "\n";
  return 0;
}