#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000020;
const int MOD = 1e9 + 7;
inline int add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline int sub(int a, int b) { return (a -= b) < 0 ? a + MOD : a; }
inline int pw(int x, int p = MOD - 2) {
  int res = 1;
  for (; p; p >>= 1, x = mul(x, x))
    if (p & 1) res = mul(res, x);
  return res;
}
int fac[MAXN], inv[MAXN];
inline void initInv(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
  inv[n] = pw(fac[n]);
  for (int i = n - 1; ~i; i--) inv[i] = mul(inv[i + 1], i + 1);
}
int n, k, pre[MAXN], suf[MAXN], y[MAXN];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k + 2; i++) y[i] = add(y[i - 1], pw(i, k));
  initInv(k + 2);
  pre[0] = suf[k + 3] = 1;
  for (int i = 1; i <= k + 2; i++) pre[i] = mul(pre[i - 1], n - i);
  for (int i = k + 2; i; i--) suf[i] = mul(suf[i + 1], n - i);
  int ans = 0;
  for (int i = 1; i <= k + 2; i++) {
    int a = mul(pre[i - 1], suf[i + 1]);
    int b = mul(((k - i) & 1 ? MOD - 1 : 1), mul(inv[i - 1], inv[k + 2 - i]));
    ans = add(ans, mul(y[i], mul(a, b)));
    ans = (ans % MOD + MOD) % MOD;
  }
  printf("%d\n", (ans % MOD + MOD) % MOD);
  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 = 1000020;
const int MOD = 1e9 + 7;
inline int add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline int sub(int a, int b) { return (a -= b) < 0 ? a + MOD : a; }
inline int pw(int x, int p = MOD - 2) {
  int res = 1;
  for (; p; p >>= 1, x = mul(x, x))
    if (p & 1) res = mul(res, x);
  return res;
}
int fac[MAXN], inv[MAXN];
inline void initInv(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
  inv[n] = pw(fac[n]);
  for (int i = n - 1; ~i; i--) inv[i] = mul(inv[i + 1], i + 1);
}
int n, k, pre[MAXN], suf[MAXN], y[MAXN];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= k + 2; i++) y[i] = add(y[i - 1], pw(i, k));
  initInv(k + 2);
  pre[0] = suf[k + 3] = 1;
  for (int i = 1; i <= k + 2; i++) pre[i] = mul(pre[i - 1], n - i);
  for (int i = k + 2; i; i--) suf[i] = mul(suf[i + 1], n - i);
  int ans = 0;
  for (int i = 1; i <= k + 2; i++) {
    int a = mul(pre[i - 1], suf[i + 1]);
    int b = mul(((k - i) & 1 ? MOD - 1 : 1), mul(inv[i - 1], inv[k + 2 - i]));
    ans = add(ans, mul(y[i], mul(a, b)));
    ans = (ans % MOD + MOD) % MOD;
  }
  printf("%d\n", (ans % MOD + MOD) % MOD);
  return 0;
}

```