#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000006;
const long long mod = 1e9 + 7;
int n, k;
long long po[maxn];
long long ne[maxn];
long long c[maxn];
long long S, Y[maxn];
long long x, y;
long long ex_gcd(long long num1, long long num2) {
  if (!num2) {
    x = 1;
    y = 0;
    return num1;
  }
  long long ans = ex_gcd(num2, num1 % num2);
  long long tmp = x;
  x = y;
  y = tmp - (num1 / num2) * x;
  return ans;
}
long long inv(long long xx) {
  ex_gcd(xx, mod);
  return (x % mod + mod) % mod;
}
void pre() {
  po[0] = ne[0] = 1;
  for (int i = 1; i <= k + 2; i++) {
    int x = mod - i;
    po[i] = (po[i - 1] * i) % mod;
    ne[i] = (ne[i - 1] * x) % mod;
  }
  for (int i = 1; i <= k + 2; i++) {
    c[i] = (inv(po[i - 1]) * inv(ne[k + 2 - i])) % mod;
  }
  S = 1;
  for (int i = n - k - 2; i <= n - 1; i++) {
    S = (S * i) % mod;
  }
}
long long pow(long long a, int k) {
  long long ret = 1;
  while (k) {
    if (k & 1) ret = (ret * a) % mod;
    a = (a * a) % mod;
    k >>= 1;
  }
  return ret;
}
int main() {
  cin >> n >> k;
  if (!k) {
    cout << n << endl;
    return 0;
  }
  for (int i = 1; i <= min(k + 2, n); i++) {
    Y[i] = (Y[i - 1] + pow(i * 1LL, k)) % mod;
  }
  if (n <= k + 2) {
    printf("%d\n", Y[n]);
    return 0;
  }
  pre();
  long long ret = 0;
  for (int i = 1; i <= k + 2; i++) {
    long long mid = (((c[i] * S) % mod) * Y[i]) % mod;
    ret = (ret + mid * inv(n - i)) % mod;
  }
  cout << ret << endl;
  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;
const int maxn = 1000006;
const long long mod = 1e9 + 7;
int n, k;
long long po[maxn];
long long ne[maxn];
long long c[maxn];
long long S, Y[maxn];
long long x, y;
long long ex_gcd(long long num1, long long num2) {
  if (!num2) {
    x = 1;
    y = 0;
    return num1;
  }
  long long ans = ex_gcd(num2, num1 % num2);
  long long tmp = x;
  x = y;
  y = tmp - (num1 / num2) * x;
  return ans;
}
long long inv(long long xx) {
  ex_gcd(xx, mod);
  return (x % mod + mod) % mod;
}
void pre() {
  po[0] = ne[0] = 1;
  for (int i = 1; i <= k + 2; i++) {
    int x = mod - i;
    po[i] = (po[i - 1] * i) % mod;
    ne[i] = (ne[i - 1] * x) % mod;
  }
  for (int i = 1; i <= k + 2; i++) {
    c[i] = (inv(po[i - 1]) * inv(ne[k + 2 - i])) % mod;
  }
  S = 1;
  for (int i = n - k - 2; i <= n - 1; i++) {
    S = (S * i) % mod;
  }
}
long long pow(long long a, int k) {
  long long ret = 1;
  while (k) {
    if (k & 1) ret = (ret * a) % mod;
    a = (a * a) % mod;
    k >>= 1;
  }
  return ret;
}
int main() {
  cin >> n >> k;
  if (!k) {
    cout << n << endl;
    return 0;
  }
  for (int i = 1; i <= min(k + 2, n); i++) {
    Y[i] = (Y[i - 1] + pow(i * 1LL, k)) % mod;
  }
  if (n <= k + 2) {
    printf("%d\n", Y[n]);
    return 0;
  }
  pre();
  long long ret = 0;
  for (int i = 1; i <= k + 2; i++) {
    long long mid = (((c[i] * S) % mod) * Y[i]) % mod;
    ret = (ret + mid * inv(n - i)) % mod;
  }
  cout << ret << endl;
  return 0;
}

```