#include <bits/stdc++.h>
const int nn = 3e6 + 10;
unsigned long long n, t, k, p, p2;
char s[nn];
unsigned long long f[nn];
int prime[nn], not_prime[nn];
unsigned long long ksm(unsigned long long a, unsigned long long b) {
  static unsigned long long ret;
  for (ret = 1; b; b >>= 1, a = a * a % p) ret = b & 1 ? ret * a % p : ret;
  return ret;
}
unsigned long long inv[nn], nfac[nn];
void init() {
  f[1] = 1;
  for (unsigned long long i = 2; i <= k + 2; i++) {
    if (!not_prime[i]) {
      prime[++prime[0]] = i;
      f[i] = ksm(i, k);
    } else {
      for (int j = 1; j <= prime[0] && i * prime[j] <= k + 1; j++) {
        not_prime[i * prime[j]] = 1;
        f[i * prime[j]] = f[i] * f[prime[j]] % p;
        if (i % prime[j] == 0) break;
      }
    }
    f[i] += f[i - 1];
    f[i] = f[i] >= p ? f[i] - p : f[i];
  }
  inv[1] = nfac[0] = nfac[1] = 1;
  for (unsigned long long i = 2; i <= k + 2; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
    nfac[i] = nfac[i - 1] * inv[i] % p;
  }
}
unsigned long long prefix[nn], suffix[nn];
unsigned long long solve(unsigned long long a) {
  prefix[1] = 1;
  for (unsigned long long i = 1; i <= k + 2; i++)
    prefix[i + 1] = prefix[i] * (a - i) % p;
  suffix[k + 2] = 1;
  for (unsigned long long i = k + 2; i >= 1; i--)
    suffix[i - 1] = suffix[i] * (a - i) % p;
  unsigned long long ret = 0, tmp;
  for (unsigned long long i = 1; i <= k + 2; i++) {
    tmp = (k + 2 - i & 1 ? p - 1 : 1) * nfac[i - 1] % p * nfac[k + 2 - i] % p;
    tmp = tmp * f[i] % p * prefix[i] % p * suffix[i] % p;
    ret = (ret + tmp) % p;
  }
  return ret;
}
int main() {
  scanf("%s %llu", s + 1, &k);
  p = 1e9 + 7;
  p2 = p * p;
  for (int i = 1; s[i] != '\0'; i++) n = (n * 10 + s[i] - '0') % p2;
  n %= p;
  init();
  if (n <= k + 1) return !printf("%llu", f[n]);
  printf("%llu", solve(n) % p);
}

### Prompt

Develop a solution in cpp to the problem described below:

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 nn = 3e6 + 10;
unsigned long long n, t, k, p, p2;
char s[nn];
unsigned long long f[nn];
int prime[nn], not_prime[nn];
unsigned long long ksm(unsigned long long a, unsigned long long b) {
  static unsigned long long ret;
  for (ret = 1; b; b >>= 1, a = a * a % p) ret = b & 1 ? ret * a % p : ret;
  return ret;
}
unsigned long long inv[nn], nfac[nn];
void init() {
  f[1] = 1;
  for (unsigned long long i = 2; i <= k + 2; i++) {
    if (!not_prime[i]) {
      prime[++prime[0]] = i;
      f[i] = ksm(i, k);
    } else {
      for (int j = 1; j <= prime[0] && i * prime[j] <= k + 1; j++) {
        not_prime[i * prime[j]] = 1;
        f[i * prime[j]] = f[i] * f[prime[j]] % p;
        if (i % prime[j] == 0) break;
      }
    }
    f[i] += f[i - 1];
    f[i] = f[i] >= p ? f[i] - p : f[i];
  }
  inv[1] = nfac[0] = nfac[1] = 1;
  for (unsigned long long i = 2; i <= k + 2; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
    nfac[i] = nfac[i - 1] * inv[i] % p;
  }
}
unsigned long long prefix[nn], suffix[nn];
unsigned long long solve(unsigned long long a) {
  prefix[1] = 1;
  for (unsigned long long i = 1; i <= k + 2; i++)
    prefix[i + 1] = prefix[i] * (a - i) % p;
  suffix[k + 2] = 1;
  for (unsigned long long i = k + 2; i >= 1; i--)
    suffix[i - 1] = suffix[i] * (a - i) % p;
  unsigned long long ret = 0, tmp;
  for (unsigned long long i = 1; i <= k + 2; i++) {
    tmp = (k + 2 - i & 1 ? p - 1 : 1) * nfac[i - 1] % p * nfac[k + 2 - i] % p;
    tmp = tmp * f[i] % p * prefix[i] % p * suffix[i] % p;
    ret = (ret + tmp) % p;
  }
  return ret;
}
int main() {
  scanf("%s %llu", s + 1, &k);
  p = 1e9 + 7;
  p2 = p * p;
  for (int i = 1; s[i] != '\0'; i++) n = (n * 10 + s[i] - '0') % p2;
  n %= p;
  init();
  if (n <= k + 1) return !printf("%llu", f[n]);
  printf("%llu", solve(n) % p);
}

```