#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
vector<long long int> f;
long long int pw(long long int a, long long int n) {
  if (n == 0) return 1;
  long long int q = pw(a, n / 2);
  q = q * q % mod;
  if (n & 1) q = q * a % mod;
  return q;
}
long long int inv(long long int a) { return pw(a, mod - 2); }
long long int mul(long long int a, long long int b) { return a * b % mod; }
int main() {
  int n, k;
  cin >> n >> k;
  f.push_back(0);
  for (int i = 1; i <= k + 1; i++) {
    f.push_back((f.back() + pw(i, k)) % mod);
  }
  if (n < k + 2) {
    cout << f[n] << endl;
    return 0;
  }
  long long int temp = 1, ans = 0;
  for (int i = 1; i <= k + 1; i++) {
    temp = mul(temp, n - i + mod);
    temp = mul(temp, inv(0 - i + mod));
  }
  for (int i = 0; i < k + 2; i++) {
    ans = (ans + mul(temp, f[i])) % mod;
    long long int q = mul(n - i + mod, i - k - 1 + mod);
    long long int w = mul(n - i - 1 + mod, i + 1 + mod);
    temp = mul(temp, q);
    temp = mul(temp, inv(w));
  }
  cout << ans << "\n";
}

### 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;
const int mod = 1e9 + 7;
vector<long long int> f;
long long int pw(long long int a, long long int n) {
  if (n == 0) return 1;
  long long int q = pw(a, n / 2);
  q = q * q % mod;
  if (n & 1) q = q * a % mod;
  return q;
}
long long int inv(long long int a) { return pw(a, mod - 2); }
long long int mul(long long int a, long long int b) { return a * b % mod; }
int main() {
  int n, k;
  cin >> n >> k;
  f.push_back(0);
  for (int i = 1; i <= k + 1; i++) {
    f.push_back((f.back() + pw(i, k)) % mod);
  }
  if (n < k + 2) {
    cout << f[n] << endl;
    return 0;
  }
  long long int temp = 1, ans = 0;
  for (int i = 1; i <= k + 1; i++) {
    temp = mul(temp, n - i + mod);
    temp = mul(temp, inv(0 - i + mod));
  }
  for (int i = 0; i < k + 2; i++) {
    ans = (ans + mul(temp, f[i])) % mod;
    long long int q = mul(n - i + mod, i - k - 1 + mod);
    long long int w = mul(n - i - 1 + mod, i + 1 + mod);
    temp = mul(temp, q);
    temp = mul(temp, inv(w));
  }
  cout << ans << "\n";
}

```