Problem: There are well-known formulas: <image>, <image>, <image>. Also mathematicians found similar formulas for higher degrees.

Find the value of the sum <image> modulo 109 + 7 (so you should find the remainder after dividing the answer by the value 109 + 7).

Input

The only line contains two integers n, k (1 ≤ n ≤ 109, 0 ≤ k ≤ 106).

Output

Print the only integer a — the remainder after dividing the value of the sum by the value 109 + 7.

Examples

Input

4 1


Output

10


Input

4 2


Output

30


Input

4 3


Output

100


Input

4 0


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a) {
  return a * a;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T>
static constexpr T inverse2(T a, T m) {
  return a <= 1 ? a : mod((1 - inverse2(m % a, a) * m) / a, m);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return inverse2(mod(a, m), m);
}
template <typename T, typename P>
static constexpr T power(T a, P b) {
  return b == 0 ? T(1) : (b % 2) ? power(a, b - 1) * a : sqr(power(a, b / 2));
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  static constexpr T reduce(T value, tag_plus) {
    return value >= Modulus ? value - Modulus : value;
  }
  static constexpr T reduce(T value, tag_minus) {
    return value < 0 ? value + Modulus : value;
  }
  static constexpr T reduce(T value, tag_good) { return value; }

 public:
  static constexpr T modulus = Modulus;
  constexpr MR() : value(0) {}
  constexpr MR(C value) : value(reduce(value % Modulus, tag_minus())) {}
  template <typename tag_t>
  constexpr MR(T value, tag_t tag) : value(reduce(value, tag)) {}
  MR &operator=(C value) {
    this->value = reduce(value % Modulus, tag_minus());
    return *this;
  }
  constexpr MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  constexpr MR operator-(MR b) const {
    return MR(value - b.value, tag_minus());
  }
  constexpr MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  constexpr MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value = reduce(value + b.value, tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value = reduce(value - b.value, tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  constexpr bool operator==(MR b) const { return value == b.value; }
  constexpr bool operator!=(MR b) const { return value != b.value; }
  constexpr T get() const { return value; }
  constexpr MR inverse() const {
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  constexpr MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
static void solve() {
  int N, K;
  cin >> N >> K;
  vector<MR<int, long long, 1000000007> > sums(K + 2);
  for (int i = 1; i <= K + 1; i++)
    sums[i] = sums[i - 1] + power(MR<int, long long, 1000000007>(i), K);
  if (N <= K + 1) {
    cout << sums[N] << '\n';
    return;
  }
  MR<int, long long, 1000000007> num = 1, den = 1;
  for (int j = 1; j <= K + 1; j++) {
    num *= N - j;
    den *= -j;
  }
  MR<int, long long, 1000000007> ans = sums[0] * num / den;
  for (int i = 1; i <= K + 1; i++) {
    num *= N - (i - 1);
    den *= N - i;
    den *= i;
    num *= (i - 1) - (K + 1);
    ans += sums[i] * num / den;
  }
  cout << ans << '\n';
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  solve();
  return 0;
}