#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 13, mod = 1e9 + 7;
int f[maxn], fac[maxn], p[maxn], q[maxn], inv[maxn], pr[maxn], fr[maxn];
bool np[maxn];
int T, k, ans;
long long n;
inline int fp(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret;
}
inline void shai_fa() {
  f[1] = 1;
  for (register int i = 2; i <= 1000011; ++i) {
    if (!np[i]) {
      pr[++pr[0]] = i;
      fr[i] = i;
    }
    for (register int j = 1; j <= pr[0] && 1ll * pr[j] * i <= 1000011; ++j) {
      np[i * pr[j]] = 1;
      fr[i * pr[j]] = pr[j];
      if (i % pr[j] == 0) break;
    }
  }
}
int main() {
  fac[0] = 1;
  for (register int i = 1; i <= 1000011; ++i)
    fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[1] = 1;
  for (register int i = 2; i <= 1000011; ++i)
    inv[i] = mod - 1ll * mod / i * inv[mod % i] % mod;
  inv[0] = 1;
  for (register int i = 2; i <= 1000011; ++i)
    inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
  shai_fa();
  scanf("%lld%d", &n, &k);
  ans = 0;
  n %= mod;
  for (register int i = 2; i <= k + 2; ++i)
    f[i] = (fr[i] == i) ? fp(i, k) : 1ll * f[i / fr[i]] * f[fr[i]] % mod;
  for (register int i = 2; i <= k + 2; ++i) f[i] = (f[i] + f[i - 1]) % mod;
  p[0] = 1;
  for (register int i = 1; i <= k + 2; ++i)
    p[i] = 1ll * p[i - 1] * (n - i + mod) % mod;
  q[k + 3] = 1;
  for (register int i = k + 2; i; --i)
    q[i] = 1ll * q[i + 1] * (n - i + mod) % mod;
  for (register int i = 1; i <= k + 2; ++i)
    ans = (ans +
           ((k - i) & 1 ? (-1ll) : 1ll) * f[i] * p[i - 1] % mod * q[i + 1] %
               mod * inv[i - 1] % mod * inv[k + 2 - i] % mod +
           mod) %
          mod;
  printf("%d\n", ans);
  return 0;
}

### Prompt

Your challenge is to write 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 maxn = 1e6 + 13, mod = 1e9 + 7;
int f[maxn], fac[maxn], p[maxn], q[maxn], inv[maxn], pr[maxn], fr[maxn];
bool np[maxn];
int T, k, ans;
long long n;
inline int fp(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret;
}
inline void shai_fa() {
  f[1] = 1;
  for (register int i = 2; i <= 1000011; ++i) {
    if (!np[i]) {
      pr[++pr[0]] = i;
      fr[i] = i;
    }
    for (register int j = 1; j <= pr[0] && 1ll * pr[j] * i <= 1000011; ++j) {
      np[i * pr[j]] = 1;
      fr[i * pr[j]] = pr[j];
      if (i % pr[j] == 0) break;
    }
  }
}
int main() {
  fac[0] = 1;
  for (register int i = 1; i <= 1000011; ++i)
    fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[1] = 1;
  for (register int i = 2; i <= 1000011; ++i)
    inv[i] = mod - 1ll * mod / i * inv[mod % i] % mod;
  inv[0] = 1;
  for (register int i = 2; i <= 1000011; ++i)
    inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
  shai_fa();
  scanf("%lld%d", &n, &k);
  ans = 0;
  n %= mod;
  for (register int i = 2; i <= k + 2; ++i)
    f[i] = (fr[i] == i) ? fp(i, k) : 1ll * f[i / fr[i]] * f[fr[i]] % mod;
  for (register int i = 2; i <= k + 2; ++i) f[i] = (f[i] + f[i - 1]) % mod;
  p[0] = 1;
  for (register int i = 1; i <= k + 2; ++i)
    p[i] = 1ll * p[i - 1] * (n - i + mod) % mod;
  q[k + 3] = 1;
  for (register int i = k + 2; i; --i)
    q[i] = 1ll * q[i + 1] * (n - i + mod) % mod;
  for (register int i = 1; i <= k + 2; ++i)
    ans = (ans +
           ((k - i) & 1 ? (-1ll) : 1ll) * f[i] * p[i - 1] % mod * q[i + 1] %
               mod * inv[i - 1] % mod * inv[k + 2 - i] % mod +
           mod) %
          mod;
  printf("%d\n", ans);
  return 0;
}

```