#include <bits/stdc++.h>
using namespace std;
const int Mod = 1000000000 + 7;
const int MAXK = 1000000;
int power(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = 1LL * ret * x % Mod;
    x = 1LL * x * x % Mod;
    k >>= 1;
  }
  return ret;
}
int n, k, ans;
int f[MAXK + 10];
int pre[MAXK + 10], suf[MAXK + 10];
int jc[MAXK + 10], fjc[MAXK + 10];
void init() {
  cin >> n >> k;
  if (n <= k + 10) {
    for (int i = 1; i <= n; i++) ans = (power(i, k) + ans) % Mod;
    cout << ans;
  } else {
    for (int i = 1; i <= k + 2; i++) f[i] = (f[i - 1] + power(i, k)) % Mod;
    pre[0] = 1;
    for (int i = 1; i <= k + 2; i++) pre[i] = 1LL * pre[i - 1] * (n - i) % Mod;
    suf[k + 3] = 1;
    for (int i = k + 2; i >= 1; i--) suf[i] = 1LL * suf[i + 1] * (n - i) % Mod;
    jc[0] = fjc[0] = 1;
    for (int i = 1; i <= k + 2; i++) {
      jc[i] = 1LL * jc[i - 1] * i % Mod;
      fjc[i] = 1LL * fjc[i - 1] * (-i + Mod) % Mod;
    }
    int l = k + 1, r = 0;
    for (int i = 1; i <= k + 2; i++) {
      int s = 1LL * pre[i - 1] * suf[i + 1] % Mod,
          m = 1LL * fjc[l] * jc[r] % Mod;
      ans = (1LL * f[i] * s % Mod * power(m, Mod - 2) % Mod + ans) % Mod;
      l--;
      r++;
    }
    cout << ans;
  }
  return;
}
int main() {
  init();
  return 0;
}

### 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;
const int Mod = 1000000000 + 7;
const int MAXK = 1000000;
int power(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = 1LL * ret * x % Mod;
    x = 1LL * x * x % Mod;
    k >>= 1;
  }
  return ret;
}
int n, k, ans;
int f[MAXK + 10];
int pre[MAXK + 10], suf[MAXK + 10];
int jc[MAXK + 10], fjc[MAXK + 10];
void init() {
  cin >> n >> k;
  if (n <= k + 10) {
    for (int i = 1; i <= n; i++) ans = (power(i, k) + ans) % Mod;
    cout << ans;
  } else {
    for (int i = 1; i <= k + 2; i++) f[i] = (f[i - 1] + power(i, k)) % Mod;
    pre[0] = 1;
    for (int i = 1; i <= k + 2; i++) pre[i] = 1LL * pre[i - 1] * (n - i) % Mod;
    suf[k + 3] = 1;
    for (int i = k + 2; i >= 1; i--) suf[i] = 1LL * suf[i + 1] * (n - i) % Mod;
    jc[0] = fjc[0] = 1;
    for (int i = 1; i <= k + 2; i++) {
      jc[i] = 1LL * jc[i - 1] * i % Mod;
      fjc[i] = 1LL * fjc[i - 1] * (-i + Mod) % Mod;
    }
    int l = k + 1, r = 0;
    for (int i = 1; i <= k + 2; i++) {
      int s = 1LL * pre[i - 1] * suf[i + 1] % Mod,
          m = 1LL * fjc[l] * jc[r] % Mod;
      ans = (1LL * f[i] * s % Mod * power(m, Mod - 2) % Mod + ans) % Mod;
      l--;
      r++;
    }
    cout << ans;
  }
  return;
}
int main() {
  init();
  return 0;
}

```