#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long)1e9 + 70;
const long long mod = 1e9 + 7;
const int maxn = 1e6 + 1000;
long long fact[maxn];
long long ifact[maxn];
long long y[maxn];
long long pw(long long a, long long n) {
  if (n == 0) return 1;
  long long b = pw(a, n >> 1);
  b = b * b % mod;
  if (n & 1) b = b * a % mod;
  return b;
}
long long tothek[maxn];
int main() {
  fact[0] = 1;
  ifact[0] = 1;
  for (int i = (1); i < (maxn); i++) {
    fact[i] = (fact[i - 1] * (long long)i) % mod;
    ifact[i] = pw(fact[i], mod - 2);
  }
  if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
  long long n;
  cin >> n;
  int(k);
  scanf("%d", &k);
  for (int i = (0); i < (k + 5); i++) {
    tothek[i] = pw(i, k);
  }
  y[0] = 0;
  for (int i = (1); i < (k + 5); i++) {
    y[i] = (y[i - 1] + tothek[i]) % mod;
  }
  k += 4;
  if (n < k) {
    long long ans = y[n];
    cout << (ans + mod) % mod << "\n";
    return 0;
  }
  long long numerator = 1;
  for (int i = (0); i < (k); i++) {
    numerator = (numerator * (long long)(n - i)) % mod;
  }
  long long ans = 0;
  for (int i = (0); i < (k); i++) {
    long long here = (numerator * pw(n - i, mod - 2)) % mod;
    here = (here * ifact[i]) % mod;
    here = (here * ifact[k - 1 - i]) % mod;
    here = (here * y[i]) % mod;
    if ((k - 1 - i) % 2 == 0) {
      ans += here;
    } else {
      ans -= here;
    }
    ans %= mod;
  }
  cout << (ans + mod) % mod << "\n";
  return 0;
}

### Prompt

Your task is to create 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 long long inf = (long long)1e9 + 70;
const long long mod = 1e9 + 7;
const int maxn = 1e6 + 1000;
long long fact[maxn];
long long ifact[maxn];
long long y[maxn];
long long pw(long long a, long long n) {
  if (n == 0) return 1;
  long long b = pw(a, n >> 1);
  b = b * b % mod;
  if (n & 1) b = b * a % mod;
  return b;
}
long long tothek[maxn];
int main() {
  fact[0] = 1;
  ifact[0] = 1;
  for (int i = (1); i < (maxn); i++) {
    fact[i] = (fact[i - 1] * (long long)i) % mod;
    ifact[i] = pw(fact[i], mod - 2);
  }
  if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
  long long n;
  cin >> n;
  int(k);
  scanf("%d", &k);
  for (int i = (0); i < (k + 5); i++) {
    tothek[i] = pw(i, k);
  }
  y[0] = 0;
  for (int i = (1); i < (k + 5); i++) {
    y[i] = (y[i - 1] + tothek[i]) % mod;
  }
  k += 4;
  if (n < k) {
    long long ans = y[n];
    cout << (ans + mod) % mod << "\n";
    return 0;
  }
  long long numerator = 1;
  for (int i = (0); i < (k); i++) {
    numerator = (numerator * (long long)(n - i)) % mod;
  }
  long long ans = 0;
  for (int i = (0); i < (k); i++) {
    long long here = (numerator * pw(n - i, mod - 2)) % mod;
    here = (here * ifact[i]) % mod;
    here = (here * ifact[k - 1 - i]) % mod;
    here = (here * y[i]) % mod;
    if ((k - 1 - i) % 2 == 0) {
      ans += here;
    } else {
      ans -= here;
    }
    ans %= mod;
  }
  cout << (ans + mod) % mod << "\n";
  return 0;
}

```