#include <bits/stdc++.h>
const int N = 1000000;
const int MOD = 1000000007;
long long power(long long x, int y) {
  long long mul = x;
  long long ret = 1;
  while (y) {
    if (y & 1) ret *= mul, ret %= MOD;
    mul *= mul;
    mul %= MOD;
    y >>= 1;
  }
  return ret;
}
int y[N + 2];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i < k + 2; i++) y[i] = (y[i - 1] + power(i, k)) % MOD;
  if (n < k + 2) return 0 * printf("%d\n", y[n]);
  long long prod = 1;
  for (int i = 0; i < k + 2; i++) prod *= (n - i), prod %= MOD;
  long long fact = 1;
  for (int i = 1; i < k + 2; i++) fact *= power(i, MOD - 2), fact %= MOD;
  long long sum = 0;
  for (int i = 0; i < k + 2; i++) {
    sum += prod * power(n - i, MOD - 2) % MOD * y[i] % MOD * fact *
           (k - i & 1 ? 1 : -1);
    sum %= MOD;
    fact *= (k + 1 - i);
    fact %= MOD;
    fact *= power(i + 1, MOD - 2);
    fact %= MOD;
  }
  if (sum < 0) sum += MOD;
  printf("%I64d\n", sum);
  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>
const int N = 1000000;
const int MOD = 1000000007;
long long power(long long x, int y) {
  long long mul = x;
  long long ret = 1;
  while (y) {
    if (y & 1) ret *= mul, ret %= MOD;
    mul *= mul;
    mul %= MOD;
    y >>= 1;
  }
  return ret;
}
int y[N + 2];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i < k + 2; i++) y[i] = (y[i - 1] + power(i, k)) % MOD;
  if (n < k + 2) return 0 * printf("%d\n", y[n]);
  long long prod = 1;
  for (int i = 0; i < k + 2; i++) prod *= (n - i), prod %= MOD;
  long long fact = 1;
  for (int i = 1; i < k + 2; i++) fact *= power(i, MOD - 2), fact %= MOD;
  long long sum = 0;
  for (int i = 0; i < k + 2; i++) {
    sum += prod * power(n - i, MOD - 2) % MOD * y[i] % MOD * fact *
           (k - i & 1 ? 1 : -1);
    sum %= MOD;
    fact *= (k + 1 - i);
    fact %= MOD;
    fact *= power(i + 1, MOD - 2);
    fact %= MOD;
  }
  if (sum < 0) sum += MOD;
  printf("%I64d\n", sum);
  return 0;
}

```