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>
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity() {
  return IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
class Zn {
 public:
  Zn() : value(0) {}
  static Zn valueOf(int value) {
    int x = value % mod();
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn valueOf(long long value) {
    int x = static_cast<int>(value % mod());
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  Zn& operator=(int rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator=(long long rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod()) {
      value -= mod();
    }
    return *this;
  }
  Zn& operator+=(int rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator+=(long long rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod();
    }
    return *this;
  }
  Zn& operator-=(int rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator-=(long long rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<long long>(value) * static_cast<long long>(rhs.value);
    value = static_cast<int>(result % mod());
    return *this;
  }
  Zn& operator*=(int rhs) { return *this *= Zn::valueOf(rhs); }
  Zn& operator*=(long long rhs) { return *this *= Zn::valueOf(rhs); }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod() - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  Zn& operator/=(int rhs) { return *this /= Zn::valueOf(rhs); }
  Zn& operator/=(long long rhs) { return *this /= Zn::valueOf(rhs); }
  bool operator==(const Zn& rhs) const { return value == rhs.value; }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod(), x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  template <typename U>
  friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
  template <typename U>
  friend std::istream& operator>>(std::istream&, Zn<U>& zn);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
  constexpr static int mod() { return T::value; }
  template <int N = T::value>
  static constexpr bool positive_or_runtime(int) {
    return N > 0;
  }
  static constexpr bool positive_or_runtime(...) { return true; }
  static_assert(
      std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
      "T::value must be int");
  static_assert(positive_or_runtime(0), "Mod has to be positive integer");
};
template <typename T>
bool operator==(const Zn<T>& lhs, int rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(int lhs, const Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator==(const Zn<T>& lhs, long long rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(long long lhs, Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, int rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(int lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, long long rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(long long rhs, const Zn<T>& lhs) {
  return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T>
Zn<T> operator+(int lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T>
Zn<T> operator+(long long lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T>
Zn<T> operator-(int lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T>
Zn<T> operator-(long lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T>
Zn<T> operator*(int lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T>
Zn<T> operator*(long long lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T>
Zn<T> operator/(int lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T>
Zn<T> operator/(long long lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
  return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
  long long value;
  stream >> value;
  zn.value = static_cast<int>(value % T::value);
  return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
  static Zn<T> identity() { return Zn<T>::valueOf(1); }
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
template <typename T>
T binpow(T base, long long power) {
  ;
  T result = identity<T>();
  while (power > 0) {
    if (power & 1) {
      result *= base;
    }
    power >>= 1;
    base *= base;
  }
  return result;
}
using namespace std;
class TaskE {
 public:
  void solve(std::istream& in, std::ostream& out) {
    using Z = ZnConst<1000000007>;
    int n, a;
    in >> n >> a;
    vector<vector<Z>> polys(a + 1);
    polys[0] = {Z::rawValueOf(1)};
    for (int i = 1; i <= a; ++i) {
      polys[i].resize(i + 1);
      for (int j = 0; j < i; ++j) {
        polys[i][j + 1] += polys[i - 1][j];
      }
      for (int j = 0; j < i; ++j) {
        polys[i][j] -= polys[i - 1][j] * (i - 1);
      }
    }
    vector<Z> cur_poly(a + 1);
    cur_poly.back() = 1;
    vector<Z> coef(a + 1);
    for (int i = a; i >= 0; --i) {
      coef[i] = cur_poly[i];
      assert(polys[i][i] == 1);
      for (int j = 0; j <= i; ++j) {
        cur_poly[j] -= coef[i] * polys[i][j];
      }
    }
    Z ans;
    for (int i = 0; i <= a; ++i) {
      Z prod = Z::valueOf(1);
      for (int t = 0; t < i; ++t) {
        prod *= (n - t);
      }
      ans += coef[i] * prod * binpow(Z::rawValueOf(2), n - i);
    }
    out << ans << "\n";
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskE solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}