#include <bits/stdc++.h>
using namespace std;
long long bigmod(int n, int p) {
  if (p == 0) return 1;
  if (n <= 1) return n;
  long long ret = bigmod(n, p >> 1);
  ret = (ret * ret) % 1000000007;
  if (p & 1) ret = (ret * n) % 1000000007;
  return ret;
}
long long f(long long n, int k) {
  long long ret = 0;
  for (int i = 1; i <= n; i++) ret = (ret + bigmod(i, k)) % 1000000007;
  return ret;
}
long long fact[2000005];
vector<pair<int, int> > v(1200000);
long long lagrange(const vector<pair<int, int> > &v, long long x) {
  long long ret = 0, lob = 1, p, q;
  for (auto i : v) lob = (lob * (x - i.first)) % 1000000007;
  int n = v.size();
  fact[0] = 1;
  for (int i = 1; i <= n + 1; i++)
    fact[i] = (fact[i - 1] * (long long)i) % 1000000007;
  for (auto i : v) {
    long long sum = i.second;
    sum = (sum * lob) % 1000000007;
    sum = (sum * bigmod(x - i.first, 1000000007 - 2)) % 1000000007;
    p = fact[i.first - v[0].first];
    q = fact[v[n - 1].first - i.first];
    if ((v[n - 1].first - i.first) % 2) q = (q * -1 + 1000000007) % 1000000007;
    sum = (sum * bigmod((p * q) % 1000000007, 1000000007 - 2)) % 1000000007;
    ret = (ret + sum) % 1000000007;
  }
  return ret;
}
void go(int n, int k) {
  v[0] = {1, 1};
  for (int i = 2; i <= n; i++) {
    v[i - 1] = {i, bigmod(i, k)};
    v[i - 1].second = (v[i - 2].second + v[i - 1].second) % 1000000007;
  }
}
int main() {
  std::ios_base::sync_with_stdio(0);
  int cases, caseno = 0, n, i, j, k, cnt, sum;
  cin >> n >> k;
  go(1200000, k);
  if (n <= 1200000)
    cout << v[n - 1].second;
  else
    cout << lagrange(v, n);
  return 0;
}

### Prompt

Please formulate 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;
long long bigmod(int n, int p) {
  if (p == 0) return 1;
  if (n <= 1) return n;
  long long ret = bigmod(n, p >> 1);
  ret = (ret * ret) % 1000000007;
  if (p & 1) ret = (ret * n) % 1000000007;
  return ret;
}
long long f(long long n, int k) {
  long long ret = 0;
  for (int i = 1; i <= n; i++) ret = (ret + bigmod(i, k)) % 1000000007;
  return ret;
}
long long fact[2000005];
vector<pair<int, int> > v(1200000);
long long lagrange(const vector<pair<int, int> > &v, long long x) {
  long long ret = 0, lob = 1, p, q;
  for (auto i : v) lob = (lob * (x - i.first)) % 1000000007;
  int n = v.size();
  fact[0] = 1;
  for (int i = 1; i <= n + 1; i++)
    fact[i] = (fact[i - 1] * (long long)i) % 1000000007;
  for (auto i : v) {
    long long sum = i.second;
    sum = (sum * lob) % 1000000007;
    sum = (sum * bigmod(x - i.first, 1000000007 - 2)) % 1000000007;
    p = fact[i.first - v[0].first];
    q = fact[v[n - 1].first - i.first];
    if ((v[n - 1].first - i.first) % 2) q = (q * -1 + 1000000007) % 1000000007;
    sum = (sum * bigmod((p * q) % 1000000007, 1000000007 - 2)) % 1000000007;
    ret = (ret + sum) % 1000000007;
  }
  return ret;
}
void go(int n, int k) {
  v[0] = {1, 1};
  for (int i = 2; i <= n; i++) {
    v[i - 1] = {i, bigmod(i, k)};
    v[i - 1].second = (v[i - 2].second + v[i - 1].second) % 1000000007;
  }
}
int main() {
  std::ios_base::sync_with_stdio(0);
  int cases, caseno = 0, n, i, j, k, cnt, sum;
  cin >> n >> k;
  go(1200000, k);
  if (n <= 1200000)
    cout << v[n - 1].second;
  else
    cout << lagrange(v, n);
  return 0;
}

```