#include <bits/stdc++.h>
using namespace std;
long long int mpow(long long int n, long long int t) {
  if (t == 0) return n == 0 ? 0 : 1;
  long long int ret = mpow(n * n % 1000000007, t / 2);
  if (t % 2 == 1) ret = ret * n % 1000000007;
  return ret;
}
long long int inv(long long int x) {
  return mpow(x % 1000000007, 1000000007 - 2);
}
long long int gt[1000005];
void make() {
  gt[1] = 1;
  for (int i = 2; i < 1000005; i++) {
    gt[i] = 1000000007 - gt[1000000007 % i] * (1000000007 / i) % 1000000007;
  }
}
int main() {
  long long int n, k;
  scanf("%lld %lld", &n, &k);
  if (n <= k + 1) {
    long long int ret = 0;
    for (long long int i = 1; i <= n; i++) {
      long long int vl = mpow(i, k);
      ret += vl;
      if (ret >= 1000000007) ret -= 1000000007;
    }
    printf("%lld\n", ret);
  } else {
    make();
    long long int mul = 1;
    for (int i = 0; i <= k + 1; i++)
      mul = mul * (long long int)(n - i) % 1000000007;
    long long int sum = 0, mt = 1;
    for (int i = 1; i <= k + 1; i++)
      mt = mt * (1000000007 - gt[i]) % 1000000007;
    long long int ret = 0;
    for (int i = 0; i <= k + 1; i++) {
      sum += mpow(i, k);
      if (sum >= 1000000007) sum -= 1000000007;
      ret += (sum * mt % 1000000007) * (mul * inv(n - i) % 1000000007) %
             1000000007;
      if (ret >= 1000000007) ret -= 1000000007;
      mt = mt * (1000000007 + i - (k + 1)) % 1000000007;
      mt = mt * gt[i + 1] % 1000000007;
    }
    printf("%lld\n", ret);
  }
  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>
using namespace std;
long long int mpow(long long int n, long long int t) {
  if (t == 0) return n == 0 ? 0 : 1;
  long long int ret = mpow(n * n % 1000000007, t / 2);
  if (t % 2 == 1) ret = ret * n % 1000000007;
  return ret;
}
long long int inv(long long int x) {
  return mpow(x % 1000000007, 1000000007 - 2);
}
long long int gt[1000005];
void make() {
  gt[1] = 1;
  for (int i = 2; i < 1000005; i++) {
    gt[i] = 1000000007 - gt[1000000007 % i] * (1000000007 / i) % 1000000007;
  }
}
int main() {
  long long int n, k;
  scanf("%lld %lld", &n, &k);
  if (n <= k + 1) {
    long long int ret = 0;
    for (long long int i = 1; i <= n; i++) {
      long long int vl = mpow(i, k);
      ret += vl;
      if (ret >= 1000000007) ret -= 1000000007;
    }
    printf("%lld\n", ret);
  } else {
    make();
    long long int mul = 1;
    for (int i = 0; i <= k + 1; i++)
      mul = mul * (long long int)(n - i) % 1000000007;
    long long int sum = 0, mt = 1;
    for (int i = 1; i <= k + 1; i++)
      mt = mt * (1000000007 - gt[i]) % 1000000007;
    long long int ret = 0;
    for (int i = 0; i <= k + 1; i++) {
      sum += mpow(i, k);
      if (sum >= 1000000007) sum -= 1000000007;
      ret += (sum * mt % 1000000007) * (mul * inv(n - i) % 1000000007) %
             1000000007;
      if (ret >= 1000000007) ret -= 1000000007;
      mt = mt * (1000000007 + i - (k + 1)) % 1000000007;
      mt = mt * gt[i + 1] % 1000000007;
    }
    printf("%lld\n", ret);
  }
  return 0;
}

```