#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
ll a[maxn];
ll c[maxn];
ll d[maxn];
ll d2[maxn];
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  ll x1, y1;
  ll d = exgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - a / b * y1;
  return d;
}
ll quick(ll n, ll k) {
  ll ans = 1, y = n;
  while (k) {
    if (k & 1) {
      ans = ans * y % mod;
    }
    k >>= 1;
    y = y * y % mod;
  }
  return ans % mod;
}
ll inv2(ll a) {
  ll x, y;
  ll d = exgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}
ll inv(int a) { return quick(a, mod - 2); }
inline void prepare() {}
inline void Solve(int cas = 1) {
  ll n, k;
  scanf("%lld", &(n)), scanf("%lld", &(k));
  a[0] = 0;
  for (ll i = 1; i <= k + 1; i++) {
    a[i] = a[i - 1];
    a[i] += quick(i, k);
    a[i] %= mod;
    if (0) {
      cout << a[i] << " " << i << endl;
    }
  }
  if (n <= k + 1) {
    printf("%lld", (a[n] % mod + mod) % mod);
    return;
  }
  c[0] = inv(1) % mod;
  d[0] = n;
  for (ll i = (1); i <= (k + 1); i++) {
    c[i] = c[i - 1] * inv(i) % mod;
    d[i] = d[i - 1] * (n - i) % mod;
  }
  d2[k + 1] = (n - (k + 1)) % mod;
  for (ll i = (k); i >= (0); i--) {
    d2[i] = d2[i + 1] * (n - i) % mod;
  }
  ll ans = 0;
  for (ll i = 0; i <= k + 1; i++) {
    ll y = 1;
    if (i - 1 >= 0) y *= d[i - 1];
    y %= mod;
    if (i + 1 <= k + 1) y *= d2[i + 1];
    y %= mod;
    y *= c[i];
    y %= mod;
    y *= c[k + 1 - i];
    if ((k + 1 - i) % 2) y = -y;
    y %= mod;
    ;
    y *= a[i];
    y %= mod;
    ans += y;
    ans %= mod;
  }
  ans = (ans % mod + mod) % mod;
  printf("%lld\n", ans);
}
inline void Solvem() {
  int T;
  scanf("%d", &(T));
  for (ll i = (1); i <= (T); i++) Solve(i);
}
int main() {
  prepare();
  Solve();
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
ll a[maxn];
ll c[maxn];
ll d[maxn];
ll d2[maxn];
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  ll x1, y1;
  ll d = exgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - a / b * y1;
  return d;
}
ll quick(ll n, ll k) {
  ll ans = 1, y = n;
  while (k) {
    if (k & 1) {
      ans = ans * y % mod;
    }
    k >>= 1;
    y = y * y % mod;
  }
  return ans % mod;
}
ll inv2(ll a) {
  ll x, y;
  ll d = exgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}
ll inv(int a) { return quick(a, mod - 2); }
inline void prepare() {}
inline void Solve(int cas = 1) {
  ll n, k;
  scanf("%lld", &(n)), scanf("%lld", &(k));
  a[0] = 0;
  for (ll i = 1; i <= k + 1; i++) {
    a[i] = a[i - 1];
    a[i] += quick(i, k);
    a[i] %= mod;
    if (0) {
      cout << a[i] << " " << i << endl;
    }
  }
  if (n <= k + 1) {
    printf("%lld", (a[n] % mod + mod) % mod);
    return;
  }
  c[0] = inv(1) % mod;
  d[0] = n;
  for (ll i = (1); i <= (k + 1); i++) {
    c[i] = c[i - 1] * inv(i) % mod;
    d[i] = d[i - 1] * (n - i) % mod;
  }
  d2[k + 1] = (n - (k + 1)) % mod;
  for (ll i = (k); i >= (0); i--) {
    d2[i] = d2[i + 1] * (n - i) % mod;
  }
  ll ans = 0;
  for (ll i = 0; i <= k + 1; i++) {
    ll y = 1;
    if (i - 1 >= 0) y *= d[i - 1];
    y %= mod;
    if (i + 1 <= k + 1) y *= d2[i + 1];
    y %= mod;
    y *= c[i];
    y %= mod;
    y *= c[k + 1 - i];
    if ((k + 1 - i) % 2) y = -y;
    y %= mod;
    ;
    y *= a[i];
    y %= mod;
    ans += y;
    ans %= mod;
  }
  ans = (ans % mod + mod) % mod;
  printf("%lld\n", ans);
}
inline void Solvem() {
  int T;
  scanf("%d", &(T));
  for (ll i = (1); i <= (T); i++) Solve(i);
}
int main() {
  prepare();
  Solve();
  return 0;
}

```