#include <bits/stdc++.h>
const long long MSQ = 1000000007LL * 1000000007LL;
inline int mul(int a, int b) { return (int)(a * 1LL * b % 1000000007LL); }
inline int powr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a);
    a = mul(a, a);
    b >>= 1;
  }
  return ans;
}
int main() {
  int n, k, i, c, d;
  long long x, y, z, u, v, res;
  scanf("%d %d", &n, &k);
  if (k == 0)
    res = n;
  else {
    if (n <= (k + 1)) {
      for (i = 1, res = 0; i <= n; i++) res += powr(i, k);
    } else {
      res = 0;
      u = 1, v = 1, z = 0;
      for (i = 0; i <= (k + 1); i++) {
        u = (u * (n - i)) % 1000000007LL;
        if (i) v = ((v * -i) + MSQ) % 1000000007LL;
      }
      for (i = 0, c = 1, d = k + 1; i <= (k + 1); i++, c++, d--) {
        z = (z + powr(i, k)) % 1000000007LL;
        x = (u * z) % 1000000007LL;
        x = (x * powr(n - i, 1000000007LL - 2)) % 1000000007LL;
        y = ((x * powr(v, 1000000007LL - 2)) % 1000000007LL);
        v = (v * c) % 1000000007LL;
        if (d) v = (v * powr(d, 1000000007LL - 2)) % 1000000007LL;
        if (i & 1) y = 1000000007LL - y;
        res += y;
      }
    }
  }
  printf("%lld\n", res % 1000000007LL);
  return 0;
}

### Prompt

Please provide a CPP coded solution 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 long long MSQ = 1000000007LL * 1000000007LL;
inline int mul(int a, int b) { return (int)(a * 1LL * b % 1000000007LL); }
inline int powr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mul(ans, a);
    a = mul(a, a);
    b >>= 1;
  }
  return ans;
}
int main() {
  int n, k, i, c, d;
  long long x, y, z, u, v, res;
  scanf("%d %d", &n, &k);
  if (k == 0)
    res = n;
  else {
    if (n <= (k + 1)) {
      for (i = 1, res = 0; i <= n; i++) res += powr(i, k);
    } else {
      res = 0;
      u = 1, v = 1, z = 0;
      for (i = 0; i <= (k + 1); i++) {
        u = (u * (n - i)) % 1000000007LL;
        if (i) v = ((v * -i) + MSQ) % 1000000007LL;
      }
      for (i = 0, c = 1, d = k + 1; i <= (k + 1); i++, c++, d--) {
        z = (z + powr(i, k)) % 1000000007LL;
        x = (u * z) % 1000000007LL;
        x = (x * powr(n - i, 1000000007LL - 2)) % 1000000007LL;
        y = ((x * powr(v, 1000000007LL - 2)) % 1000000007LL);
        v = (v * c) % 1000000007LL;
        if (d) v = (v * powr(d, 1000000007LL - 2)) % 1000000007LL;
        if (i & 1) y = 1000000007LL - y;
        res += y;
      }
    }
  }
  printf("%lld\n", res % 1000000007LL);
  return 0;
}

```