#include <bits/stdc++.h>
using namespace std;
int md = (int)1e9 + 7;
int binpow(int a, int n) {
  int res = 1;
  while (n) {
    if (n & 1) {
      res = (1LL * res * a) % md;
    }
    a = (1LL * a * a) % md;
    n >>= 1;
  }
  return res;
}
const int N = 1e7 + 15;
int pref[N], suf[N];
int xes[N], yes[N];
int pref1[N], suf1[N];
int cnk(int n, int k) {
  return (1LL * pref[n] % md * suf[n - k] % md * suf[k] % md) % md;
}
void precalc() {
  pref[0] = 1;
  pref[1] = 1;
  for (int i = 2; i < N + 1; i++) {
    pref[i] = (1LL * pref[i - 1] * i) % md;
  }
  suf[0] = 1;
  suf[N] = binpow(pref[N], md - 2);
  for (int i = N - 1; i >= 1; i--) {
    suf[i] = (1LL * suf[i + 1] * (i + 1)) % md;
  }
}
int slowSol(int n, int k) {
  int ans = 0;
  for (int i = 1; i < n + 1; i++) {
    ans = (ans % md + binpow(i, k) % md) % md;
  }
  return ans;
}
int main() {
  precalc();
  int n, k;
  cin >> n >> k;
  int cntp = k + 2;
  int degree = k + 1;
  xes[1] = 1;
  yes[1] = 1;
  for (int i = 2; i < cntp + 1; i++) {
    xes[i] = i;
    yes[i] = (1LL * yes[i - 1] + binpow(i, k)) % md;
  }
  if (n <= cntp) {
    return cout << yes[n], 0;
  }
  pref1[1] = (n - 1) % md;
  pref1[0] = 1;
  for (int i = 2; i < cntp + 1; i++) {
    pref1[i] = (1LL * pref1[i - 1] * (n - i)) % md;
  }
  suf1[cntp] = (n - cntp) % md;
  suf1[cntp + 1] = 1;
  for (int i = cntp - 1; i >= 1; i--) {
    suf1[i] = (1LL * suf1[i + 1] * (n - i)) % md;
  }
  long long ans = 0;
  long long chisel = 0, znam = 0;
  for (int i = 1; i < cntp + 1; i++) {
    chisel = ((1LL * pref1[i - 1] * suf1[i + 1]) % md *
                  ((cntp - i) % 2 == 0 ? 1 : -1) +
              md) %
             md;
    znam = (1LL * suf[cntp - i] * suf[i - 1]) % md;
    ans += ((1LL * yes[i] * chisel) % md * znam % md) % md;
    ans %= md;
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
int md = (int)1e9 + 7;
int binpow(int a, int n) {
  int res = 1;
  while (n) {
    if (n & 1) {
      res = (1LL * res * a) % md;
    }
    a = (1LL * a * a) % md;
    n >>= 1;
  }
  return res;
}
const int N = 1e7 + 15;
int pref[N], suf[N];
int xes[N], yes[N];
int pref1[N], suf1[N];
int cnk(int n, int k) {
  return (1LL * pref[n] % md * suf[n - k] % md * suf[k] % md) % md;
}
void precalc() {
  pref[0] = 1;
  pref[1] = 1;
  for (int i = 2; i < N + 1; i++) {
    pref[i] = (1LL * pref[i - 1] * i) % md;
  }
  suf[0] = 1;
  suf[N] = binpow(pref[N], md - 2);
  for (int i = N - 1; i >= 1; i--) {
    suf[i] = (1LL * suf[i + 1] * (i + 1)) % md;
  }
}
int slowSol(int n, int k) {
  int ans = 0;
  for (int i = 1; i < n + 1; i++) {
    ans = (ans % md + binpow(i, k) % md) % md;
  }
  return ans;
}
int main() {
  precalc();
  int n, k;
  cin >> n >> k;
  int cntp = k + 2;
  int degree = k + 1;
  xes[1] = 1;
  yes[1] = 1;
  for (int i = 2; i < cntp + 1; i++) {
    xes[i] = i;
    yes[i] = (1LL * yes[i - 1] + binpow(i, k)) % md;
  }
  if (n <= cntp) {
    return cout << yes[n], 0;
  }
  pref1[1] = (n - 1) % md;
  pref1[0] = 1;
  for (int i = 2; i < cntp + 1; i++) {
    pref1[i] = (1LL * pref1[i - 1] * (n - i)) % md;
  }
  suf1[cntp] = (n - cntp) % md;
  suf1[cntp + 1] = 1;
  for (int i = cntp - 1; i >= 1; i--) {
    suf1[i] = (1LL * suf1[i + 1] * (n - i)) % md;
  }
  long long ans = 0;
  long long chisel = 0, znam = 0;
  for (int i = 1; i < cntp + 1; i++) {
    chisel = ((1LL * pref1[i - 1] * suf1[i + 1]) % md *
                  ((cntp - i) % 2 == 0 ? 1 : -1) +
              md) %
             md;
    znam = (1LL * suf[cntp - i] * suf[i - 1]) % md;
    ans += ((1LL * yes[i] * chisel) % md * znam % md) % md;
    ans %= md;
  }
  cout << ans << "\n";
  return 0;
}

```