#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, K = 1e6 + 10, K_ = 1e6 + 5;
long long n, k;
long long idk[K], fac[K], pre[K], nxt[K], ifac[K];
int p[K];
bitset<K> np;
inline long long qpow(long long a, int x) {
  long long res = 1;
  for (; x; x >>= 1) (x & 1) && (res = res * a % MOD), a = a * a % MOD;
  return res;
}
inline void prepare() {
  np[1] = idk[1] = 1;
  for (int i = 2, ni; i <= K_; ++i) {
    if (!np[i]) {
      p[++p[0]] = i;
      idk[i] = qpow(i, k);
    }
    for (int j = 1; j <= p[0] && (ni = i * p[j]) <= K_; ++j) {
      np[ni] = 1;
      idk[ni] = idk[i] * idk[p[j]] % MOD;
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 2; i <= K_; ++i) (idk[i] += idk[i - 1]) %= MOD;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= K_; ++i) fac[i] = fac[i - 1] * i % MOD;
  ifac[K_] = qpow(fac[K_], MOD - 2);
  for (int i = K_ - 1; i >= 1; --i) ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}
inline long long getsumk(int n) {
  long long res = 0;
  pre[0] = nxt[k + 3] = 1;
  for (int i = 1; i <= k + 2; ++i) pre[i] = pre[i - 1] * (n - i) % MOD;
  for (int i = k + 2; i >= 1; --i) nxt[i] = nxt[i + 1] * (n - i) % MOD;
  for (int i = 1; i <= k + 2; ++i)
    (res += idk[i] * ifac[i - 1] % MOD * ifac[k + 2 - i] % MOD * pre[i - 1] %
            MOD * nxt[i + 1] % MOD * (k + 2 - i & 1 ? -1 : 1)) %= MOD;
  return res;
}
int main() {
  scanf("%lld%lld", &n, &k);
  prepare();
  printf("%lld\n", (getsumk(n) + MOD) % MOD);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 MOD = 1e9 + 7, K = 1e6 + 10, K_ = 1e6 + 5;
long long n, k;
long long idk[K], fac[K], pre[K], nxt[K], ifac[K];
int p[K];
bitset<K> np;
inline long long qpow(long long a, int x) {
  long long res = 1;
  for (; x; x >>= 1) (x & 1) && (res = res * a % MOD), a = a * a % MOD;
  return res;
}
inline void prepare() {
  np[1] = idk[1] = 1;
  for (int i = 2, ni; i <= K_; ++i) {
    if (!np[i]) {
      p[++p[0]] = i;
      idk[i] = qpow(i, k);
    }
    for (int j = 1; j <= p[0] && (ni = i * p[j]) <= K_; ++j) {
      np[ni] = 1;
      idk[ni] = idk[i] * idk[p[j]] % MOD;
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 2; i <= K_; ++i) (idk[i] += idk[i - 1]) %= MOD;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= K_; ++i) fac[i] = fac[i - 1] * i % MOD;
  ifac[K_] = qpow(fac[K_], MOD - 2);
  for (int i = K_ - 1; i >= 1; --i) ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}
inline long long getsumk(int n) {
  long long res = 0;
  pre[0] = nxt[k + 3] = 1;
  for (int i = 1; i <= k + 2; ++i) pre[i] = pre[i - 1] * (n - i) % MOD;
  for (int i = k + 2; i >= 1; --i) nxt[i] = nxt[i + 1] * (n - i) % MOD;
  for (int i = 1; i <= k + 2; ++i)
    (res += idk[i] * ifac[i - 1] % MOD * ifac[k + 2 - i] % MOD * pre[i - 1] %
            MOD * nxt[i + 1] % MOD * (k + 2 - i & 1 ? -1 : 1)) %= MOD;
  return res;
}
int main() {
  scanf("%lld%lld", &n, &k);
  prepare();
  printf("%lld\n", (getsumk(n) + MOD) % MOD);
  return 0;
}

```