#include <bits/stdc++.h>
using namespace std;
long long f[1000005];
long long fac[1000005];
long long inv[1000005];
long long part(long long a, long int b) {
  long long result = 1;
  while (b) {
    if (b % 2) result = result * a % 1000000007;
    b = b / 2;
    a = a * a % 1000000007;
  }
  if (result < 0) result += 1000000007;
  return result;
}
void init(int tot) {
  fac[0] = 1;
  for (int i = 1; i <= tot; i++) fac[i] = fac[i - 1] * i % 1000000007;
  inv[tot] = part(fac[tot], 1000000005);
  inv[0] = 1;
  for (int i = tot - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % 1000000007;
}
long long Lagrange(long int n, long int k) {
  int tot = k + 1;
  init(tot);
  long long result = 0;
  long long now = 1;
  for (int i = 1; i <= tot; i++) now = now * (n - i) % 1000000007;
  for (int i = 1; i <= tot; i++) {
    long long inv1 = part(n - i, 1000000005);
    long long inv2 = inv[i - 1] * inv[tot - i] % 1000000007;
    if ((tot - i) % 2) inv2 = 1000000007 - inv2;
    long long temp = now * inv1 % 1000000007;
    temp = temp * f[i] % 1000000007 * inv2 % 1000000007;
    result += temp;
    if (result >= 1000000007) result -= 1000000007;
  }
  return result;
}
int main() {
  long long n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + 2; i++) f[i] = (f[i - 1] + part(i, k)) % 1000000007;
  if (n <= k + 2)
    cout << f[n] << endl;
  else
    cout << Lagrange(n, k + 1) << endl;
  return 0;
}

### Prompt

Create a solution in cpp for 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;
long long f[1000005];
long long fac[1000005];
long long inv[1000005];
long long part(long long a, long int b) {
  long long result = 1;
  while (b) {
    if (b % 2) result = result * a % 1000000007;
    b = b / 2;
    a = a * a % 1000000007;
  }
  if (result < 0) result += 1000000007;
  return result;
}
void init(int tot) {
  fac[0] = 1;
  for (int i = 1; i <= tot; i++) fac[i] = fac[i - 1] * i % 1000000007;
  inv[tot] = part(fac[tot], 1000000005);
  inv[0] = 1;
  for (int i = tot - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % 1000000007;
}
long long Lagrange(long int n, long int k) {
  int tot = k + 1;
  init(tot);
  long long result = 0;
  long long now = 1;
  for (int i = 1; i <= tot; i++) now = now * (n - i) % 1000000007;
  for (int i = 1; i <= tot; i++) {
    long long inv1 = part(n - i, 1000000005);
    long long inv2 = inv[i - 1] * inv[tot - i] % 1000000007;
    if ((tot - i) % 2) inv2 = 1000000007 - inv2;
    long long temp = now * inv1 % 1000000007;
    temp = temp * f[i] % 1000000007 * inv2 % 1000000007;
    result += temp;
    if (result >= 1000000007) result -= 1000000007;
  }
  return result;
}
int main() {
  long long n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + 2; i++) f[i] = (f[i - 1] + part(i, k)) % 1000000007;
  if (n <= k + 2)
    cout << f[n] << endl;
  else
    cout << Lagrange(n, k + 1) << endl;
  return 0;
}

```