#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, k, a[N], inv[N], ans;
int pw(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = (long long)ret * x % mod;
    x = (long long)x * x % mod;
    k >>= 1;
  }
  return ret;
}
void upd(int &x) { x >= mod ? x -= mod : 0; }
int main() {
  scanf("%d%d", &n, &k);
  int lm = k + 2;
  if (n <= lm) {
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + pw(i, k), upd(a[i]);
    printf("%d\n", a[n]);
    return 0;
  }
  for (int i = 1; i <= lm; i++) inv[i] = pw(i, mod - 2);
  int s0 = 1;
  for (int i = 1; i <= lm; i++) s0 = (long long)s0 * (n - i) % mod;
  int s1 = 1, fx = ((lm - 1) & 1 ? -1 : 1);
  for (int i = 2; i <= lm; i++) s1 = (long long)s1 * (i - 1) % mod;
  a[1] = 1;
  ans = (long long)s0 * pw(n - 1, mod - 2) % mod * fx * pw(s1, mod - 2) % mod *
        a[1] % mod;
  for (int i = 2; i <= lm; i++) {
    a[i] = a[i - 1] + pw(i, k);
    upd(a[i]);
    fx = -fx;
    s1 = (long long)s1 * (i - 1) % mod * inv[lm - i + 1] % mod;
    ans = (ans + (long long)s0 * pw(n - i, mod - 2) % mod * fx *
                     pw(s1, mod - 2) % mod * a[i]) %
          mod;
  }
  printf("%d\n", ans < 0 ? ans + mod : ans);
  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;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, k, a[N], inv[N], ans;
int pw(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = (long long)ret * x % mod;
    x = (long long)x * x % mod;
    k >>= 1;
  }
  return ret;
}
void upd(int &x) { x >= mod ? x -= mod : 0; }
int main() {
  scanf("%d%d", &n, &k);
  int lm = k + 2;
  if (n <= lm) {
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + pw(i, k), upd(a[i]);
    printf("%d\n", a[n]);
    return 0;
  }
  for (int i = 1; i <= lm; i++) inv[i] = pw(i, mod - 2);
  int s0 = 1;
  for (int i = 1; i <= lm; i++) s0 = (long long)s0 * (n - i) % mod;
  int s1 = 1, fx = ((lm - 1) & 1 ? -1 : 1);
  for (int i = 2; i <= lm; i++) s1 = (long long)s1 * (i - 1) % mod;
  a[1] = 1;
  ans = (long long)s0 * pw(n - 1, mod - 2) % mod * fx * pw(s1, mod - 2) % mod *
        a[1] % mod;
  for (int i = 2; i <= lm; i++) {
    a[i] = a[i - 1] + pw(i, k);
    upd(a[i]);
    fx = -fx;
    s1 = (long long)s1 * (i - 1) % mod * inv[lm - i + 1] % mod;
    ans = (ans + (long long)s0 * pw(n - i, mod - 2) % mod * fx *
                     pw(s1, mod - 2) % mod * a[i]) %
          mod;
  }
  printf("%d\n", ans < 0 ? ans + mod : ans);
  return 0;
}

```