#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 3;
const long long P = 1e9 + 7;
int k, pri[M], tp;
bool isnp[M];
long long n;
int y[M], suf[M], fac[M], ifac[M];
long long qpow(long long a, long long b) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % P)
    if (b & 1) res = res * a % P;
  return res;
}
void init() {
  y[1] = 1;
  for (register int i = 2; i <= k + 1; i++) {
    if (!isnp[i]) {
      y[i] = qpow(i, k);
      pri[++tp] = i;
    }
    for (register int j = 1; j <= tp; j++) {
      int q = pri[j] * i;
      if (q > k + 1) break;
      y[q] = 1ll * y[i] * y[pri[j]] % P;
      isnp[q] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  for (register int i = 1; i <= k + 1; i++) {
    y[i] += y[i - 1];
    if (y[i] >= P) y[i] -= P;
  }
  fac[0] = suf[k + 2] = 1;
  for (register int i = k + 1; i; i--) suf[i] = suf[i + 1] * (n - i) % P;
  for (register int i = 1; i <= k + 1; i++) fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[k + 1] = qpow(fac[k + 1], P - 2);
  for (register int i = k; ~i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
}
int main() {
  scanf("%lld%d", &n, &k);
  init();
  long long ans = 0, pre = 1, nw = k & 1 ? 1 : -1;
  for (register int i = 0; i <= k + 1; i++, nw = -nw) {
    ans = (ans + nw * y[i] * pre % P * suf[i + 1] % P * ifac[i] % P *
                     ifac[k + 1 - i]) %
          P;
    pre = pre * (n - i) % P;
  }
  printf("%lld", ans < 0 ? ans + P : ans);
  return 0;
}

### Prompt

Generate 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 M = 1e6 + 3;
const long long P = 1e9 + 7;
int k, pri[M], tp;
bool isnp[M];
long long n;
int y[M], suf[M], fac[M], ifac[M];
long long qpow(long long a, long long b) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % P)
    if (b & 1) res = res * a % P;
  return res;
}
void init() {
  y[1] = 1;
  for (register int i = 2; i <= k + 1; i++) {
    if (!isnp[i]) {
      y[i] = qpow(i, k);
      pri[++tp] = i;
    }
    for (register int j = 1; j <= tp; j++) {
      int q = pri[j] * i;
      if (q > k + 1) break;
      y[q] = 1ll * y[i] * y[pri[j]] % P;
      isnp[q] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  for (register int i = 1; i <= k + 1; i++) {
    y[i] += y[i - 1];
    if (y[i] >= P) y[i] -= P;
  }
  fac[0] = suf[k + 2] = 1;
  for (register int i = k + 1; i; i--) suf[i] = suf[i + 1] * (n - i) % P;
  for (register int i = 1; i <= k + 1; i++) fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[k + 1] = qpow(fac[k + 1], P - 2);
  for (register int i = k; ~i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
}
int main() {
  scanf("%lld%d", &n, &k);
  init();
  long long ans = 0, pre = 1, nw = k & 1 ? 1 : -1;
  for (register int i = 0; i <= k + 1; i++, nw = -nw) {
    ans = (ans + nw * y[i] * pre % P * suf[i + 1] % P * ifac[i] % P *
                     ifac[k + 1 - i]) %
          P;
    pre = pre * (n - i) % P;
  }
  printf("%lld", ans < 0 ? ans + P : ans);
  return 0;
}

```