#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
const int N = 1e6 + 10;
int n, k;
int ifac[N];
void pre() {
  ifac[0] = ifac[1] = 1;
  for (int i = 2; i < N; i++) {
    ifac[i] = -1LL * P / i * ifac[P % i] % P;
  }
  for (int i = 2; i < N; i++) {
    ifac[i] = 1LL * ifac[i] * ifac[i - 1] % P;
  }
}
int ksm(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1LL * a * a % P) {
    if (b & 1) ret = 1LL * ret * a % P;
  }
  return ret;
}
struct qm {
  vector<int> y;
  int a[N], b[N];
  void init(int k) {
    y.resize(1);
    y[0] = 0;
    for (int i = 1; i <= k + 1; i++) {
      y.push_back((y.back() + ksm(i, k)) % P);
    }
  }
  int Lagrange(long long X) {
    int n = (int)y.size() - 1, ans = 0;
    X %= P;
    a[0] = (int)X;
    b[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
      a[i] = 1LL * a[i - 1] * (X - i) % P;
    }
    for (int i = n; i >= 0; i--) {
      b[i] = 1LL * b[i + 1] * (X - i) % P;
    }
    for (int i = 0; i <= n; i++)
      (ans += 1LL * y[i] * (i == 0 ? 1 : a[i - 1]) % P * b[i + 1] % P *
              ifac[i] % P * (((n - i) & 1) ? -1 : 1) * ifac[n - i] % P) %= P;
    return (ans + P) % P;
  }
  int solve(long long n) { return Lagrange(n); }
} I;
int main() {
  pre();
  scanf("%d%d", &n, &k);
  I.init(k);
  printf("%d\n", I.solve(n));
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
const int P = 1e9 + 7;
const int N = 1e6 + 10;
int n, k;
int ifac[N];
void pre() {
  ifac[0] = ifac[1] = 1;
  for (int i = 2; i < N; i++) {
    ifac[i] = -1LL * P / i * ifac[P % i] % P;
  }
  for (int i = 2; i < N; i++) {
    ifac[i] = 1LL * ifac[i] * ifac[i - 1] % P;
  }
}
int ksm(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1LL * a * a % P) {
    if (b & 1) ret = 1LL * ret * a % P;
  }
  return ret;
}
struct qm {
  vector<int> y;
  int a[N], b[N];
  void init(int k) {
    y.resize(1);
    y[0] = 0;
    for (int i = 1; i <= k + 1; i++) {
      y.push_back((y.back() + ksm(i, k)) % P);
    }
  }
  int Lagrange(long long X) {
    int n = (int)y.size() - 1, ans = 0;
    X %= P;
    a[0] = (int)X;
    b[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
      a[i] = 1LL * a[i - 1] * (X - i) % P;
    }
    for (int i = n; i >= 0; i--) {
      b[i] = 1LL * b[i + 1] * (X - i) % P;
    }
    for (int i = 0; i <= n; i++)
      (ans += 1LL * y[i] * (i == 0 ? 1 : a[i - 1]) % P * b[i + 1] % P *
              ifac[i] % P * (((n - i) & 1) ? -1 : 1) * ifac[n - i] % P) %= P;
    return (ans + P) % P;
  }
  int solve(long long n) { return Lagrange(n); }
} I;
int main() {
  pre();
  scanf("%d%d", &n, &k);
  I.init(k);
  printf("%d\n", I.solve(n));
  return 0;
}

```