#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int const nmax = 1000000;
int const modulo = 1000000007;
class ModuloRing {
 private:
  void gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
      x = 1;
      y = 0;
    } else {
      gcd(b, a % b, x, y);
      int aux = x;
      x = y;
      y = aux - a / b * y;
    }
  }

 public:
  int number;
  ModuloRing(int number_ = 0) {
    if (number_ < 0)
      number = number_ % modulo + modulo;
    else
      number = number_ % modulo;
  }
  ModuloRing(ll number_) { number = number_ % modulo; }
  ModuloRing operator+(ModuloRing const &a) const { return number + a.number; }
  ModuloRing operator-(ModuloRing const &a) const {
    return modulo + number - a.number;
  }
  ModuloRing operator*(ModuloRing const &a) const {
    return 1LL * number * a.number;
  }
  ModuloRing operator/(ModuloRing const &a) {
    int x, y;
    gcd(a.number, modulo, x, y);
    x %= modulo;
    if (x < 0) x += modulo;
    return 1LL * number * x;
  }
};
ModuloRing lgpow(ModuloRing a, int b) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a;
  else {
    ModuloRing result = lgpow(a, b / 2);
    if (b % 2 == 0)
      return result * result;
    else
      return result * result * a;
  }
}
ModuloRing eval[5 + nmax];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + 2; i++) eval[i] = eval[i - 1] + lgpow(i, k);
  if (n <= k + 2)
    cout << eval[n].number;
  else {
    ModuloRing result;
    ModuloRing prod(1);
    for (int i = 1; i <= k + 2; i++) prod = prod * (n - i);
    for (int i = 2; i <= k + 2; i++) prod = prod / (1 - i);
    result = result + eval[1] * prod / (n - 1);
    for (int i = 2; i <= k + 2; i++) {
      prod = prod / (i - 1) * ((i - 1) - (k + 2));
      result = result + eval[i] * prod / (n - i);
    }
    cout << result.number;
  }
  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;
int const nmax = 1000000;
int const modulo = 1000000007;
class ModuloRing {
 private:
  void gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
      x = 1;
      y = 0;
    } else {
      gcd(b, a % b, x, y);
      int aux = x;
      x = y;
      y = aux - a / b * y;
    }
  }

 public:
  int number;
  ModuloRing(int number_ = 0) {
    if (number_ < 0)
      number = number_ % modulo + modulo;
    else
      number = number_ % modulo;
  }
  ModuloRing(ll number_) { number = number_ % modulo; }
  ModuloRing operator+(ModuloRing const &a) const { return number + a.number; }
  ModuloRing operator-(ModuloRing const &a) const {
    return modulo + number - a.number;
  }
  ModuloRing operator*(ModuloRing const &a) const {
    return 1LL * number * a.number;
  }
  ModuloRing operator/(ModuloRing const &a) {
    int x, y;
    gcd(a.number, modulo, x, y);
    x %= modulo;
    if (x < 0) x += modulo;
    return 1LL * number * x;
  }
};
ModuloRing lgpow(ModuloRing a, int b) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a;
  else {
    ModuloRing result = lgpow(a, b / 2);
    if (b % 2 == 0)
      return result * result;
    else
      return result * result * a;
  }
}
ModuloRing eval[5 + nmax];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + 2; i++) eval[i] = eval[i - 1] + lgpow(i, k);
  if (n <= k + 2)
    cout << eval[n].number;
  else {
    ModuloRing result;
    ModuloRing prod(1);
    for (int i = 1; i <= k + 2; i++) prod = prod * (n - i);
    for (int i = 2; i <= k + 2; i++) prod = prod / (1 - i);
    result = result + eval[1] * prod / (n - 1);
    for (int i = 2; i <= k + 2; i++) {
      prod = prod / (i - 1) * ((i - 1) - (k + 2));
      result = result + eval[i] * prod / (n - i);
    }
    cout << result.number;
  }
  return 0;
}

```