#include <bits/stdc++.h>
using namespace std;
int n, k, inv[1000010], p[1000010], pn, f[1000010], sum1[1000010],
    sum2[1000010];
int getint() {
  int x, f = 1;
  char ch;
  while (!isdigit(ch = getchar())) f = ch == '-' ? -1 : 1;
  x = ch - '0';
  while (isdigit(ch = getchar())) x = x * 10 + ch - '0';
  return f * x;
}
int qpow(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = (1LL * (a) * (a) % 1000000007))
    if (b & 1) ans = (1LL * (ans) * (a) % 1000000007);
  return ans;
}
void shaker(int n) {
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!f[i]) f[p[++pn] = i] = qpow(i, k);
    for (int j = 1; j <= pn; j++) {
      int x = i * p[j];
      if (x > n) break;
      f[x] = (1LL * (f[i]) * (f[p[j]]) % 1000000007);
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 1; i <= n; i++) (((f[i]) += (f[i - 1])) %= 1000000007);
}
int main() {
  ((n) = getint()), ((k) = getint());
  shaker(k + 1);
  if (n <= k + 1) return printf("%d\n", f[n]), 0;
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= k + 1; i++)
    inv[i] =
        1LL * (1000000007 - 1000000007 / i) * inv[1000000007 % i] % 1000000007;
  for (int i = 2; i <= k + 1; i++)
    inv[i] = (1LL * (inv[i - 1]) * (inv[i]) % 1000000007);
  sum1[0] = n - 0, sum2[k + 1] = n - (k + 1);
  for (int i = 1; i <= k + 1; i++)
    sum1[i] = (1LL * (sum1[i - 1]) * (n - i) % 1000000007);
  for (int i = k; i >= 0; i--)
    sum2[i] = (1LL * (sum2[i + 1]) * (n - i) % 1000000007);
  int ans = 0;
  for (int i = 0; i <= k + 1; i++) {
    int a, b = 1;
    a = (1LL * (i ? sum1[i - 1] : 1) * (i != k + 1 ? sum2[i + 1] : 1) %
         1000000007);
    b = (1LL * (i ? inv[i] : 1) * (i != k + 1 ? inv[k + 1 - i] : 1) %
         1000000007);
    if ((k + 1 - i) % 2 == 1) b = 1000000007 - b;
    (((ans) += ((1LL * (f[i]) * ((1LL * (a) * (b) % 1000000007)) %
                 1000000007))) %= 1000000007);
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please formulate 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;
int n, k, inv[1000010], p[1000010], pn, f[1000010], sum1[1000010],
    sum2[1000010];
int getint() {
  int x, f = 1;
  char ch;
  while (!isdigit(ch = getchar())) f = ch == '-' ? -1 : 1;
  x = ch - '0';
  while (isdigit(ch = getchar())) x = x * 10 + ch - '0';
  return f * x;
}
int qpow(int a, int b) {
  int ans = 1;
  for (; b; b >>= 1, a = (1LL * (a) * (a) % 1000000007))
    if (b & 1) ans = (1LL * (ans) * (a) % 1000000007);
  return ans;
}
void shaker(int n) {
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!f[i]) f[p[++pn] = i] = qpow(i, k);
    for (int j = 1; j <= pn; j++) {
      int x = i * p[j];
      if (x > n) break;
      f[x] = (1LL * (f[i]) * (f[p[j]]) % 1000000007);
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 1; i <= n; i++) (((f[i]) += (f[i - 1])) %= 1000000007);
}
int main() {
  ((n) = getint()), ((k) = getint());
  shaker(k + 1);
  if (n <= k + 1) return printf("%d\n", f[n]), 0;
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= k + 1; i++)
    inv[i] =
        1LL * (1000000007 - 1000000007 / i) * inv[1000000007 % i] % 1000000007;
  for (int i = 2; i <= k + 1; i++)
    inv[i] = (1LL * (inv[i - 1]) * (inv[i]) % 1000000007);
  sum1[0] = n - 0, sum2[k + 1] = n - (k + 1);
  for (int i = 1; i <= k + 1; i++)
    sum1[i] = (1LL * (sum1[i - 1]) * (n - i) % 1000000007);
  for (int i = k; i >= 0; i--)
    sum2[i] = (1LL * (sum2[i + 1]) * (n - i) % 1000000007);
  int ans = 0;
  for (int i = 0; i <= k + 1; i++) {
    int a, b = 1;
    a = (1LL * (i ? sum1[i - 1] : 1) * (i != k + 1 ? sum2[i + 1] : 1) %
         1000000007);
    b = (1LL * (i ? inv[i] : 1) * (i != k + 1 ? inv[k + 1 - i] : 1) %
         1000000007);
    if ((k + 1 - i) % 2 == 1) b = 1000000007 - b;
    (((ans) += ((1LL * (f[i]) * ((1LL * (a) * (b) % 1000000007)) %
                 1000000007))) %= 1000000007);
  }
  printf("%d\n", ans);
  return 0;
}

```