#include <bits/stdc++.h>
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = (_tmp * _tmp) % _mod;
  if (_x & 1) _tmp = (_tmp * _a) % _mod;
  return _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x + _y;
  if (_ >= _mod) _ -= _mod;
  return _;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x - _y;
  if (_ < 0) _ += _mod;
  return _;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x * _y;
  if (_ >= _mod) _ %= _mod;
  return _;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
long long n, k, a[1010101];
void build() {}
void init() {
  n = getint();
  k = getint();
}
void solve() {
  if (k == 0) {
    cout << n << endl;
    return;
  }
  for (int i = 1; i <= k + 1; i++)
    a[i] = add(a[i - 1], mypow(i, k, 1000000007ll));
  if (n <= k + 1) {
    printf("%lld\n", a[n]);
    exit(0);
  }
  long long u = 1ll;
  for (int i = 1; i <= k + 1; i++) u = mul(u, n - i);
  long long d = 1ll;
  for (int i = 1; i <= k + 1; i++) d = mul(d, 1000000007ll - i);
  long long coe = mul(u, mypow(d, 1000000007ll - 2, 1000000007ll));
  long long ans = 0ll;
  for (int i = 1, now = k + 1; i <= k + 1; i++, now--) {
    coe = mul(coe, mul(n - (i - 1), 1000000007ll - now));
    coe = mul(coe, mypow(mul(n - i, i), 1000000007ll - 2, 1000000007ll));
    ans = add(ans, mul(coe, a[i]));
  }
  cout << ans << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = (_tmp * _tmp) % _mod;
  if (_x & 1) _tmp = (_tmp * _a) % _mod;
  return _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x + _y;
  if (_ >= _mod) _ -= _mod;
  return _;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x - _y;
  if (_ < 0) _ += _mod;
  return _;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x * _y;
  if (_ >= _mod) _ %= _mod;
  return _;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
long long n, k, a[1010101];
void build() {}
void init() {
  n = getint();
  k = getint();
}
void solve() {
  if (k == 0) {
    cout << n << endl;
    return;
  }
  for (int i = 1; i <= k + 1; i++)
    a[i] = add(a[i - 1], mypow(i, k, 1000000007ll));
  if (n <= k + 1) {
    printf("%lld\n", a[n]);
    exit(0);
  }
  long long u = 1ll;
  for (int i = 1; i <= k + 1; i++) u = mul(u, n - i);
  long long d = 1ll;
  for (int i = 1; i <= k + 1; i++) d = mul(d, 1000000007ll - i);
  long long coe = mul(u, mypow(d, 1000000007ll - 2, 1000000007ll));
  long long ans = 0ll;
  for (int i = 1, now = k + 1; i <= k + 1; i++, now--) {
    coe = mul(coe, mul(n - (i - 1), 1000000007ll - now));
    coe = mul(coe, mypow(mul(n - i, i), 1000000007ll - 2, 1000000007ll));
    ans = add(ans, mul(coe, a[i]));
  }
  cout << ans << endl;
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

```