#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long y[1000026 + 10];
long long jc[1000026 + 10], fjc[1000026 + 10], a[1000026 + 10], b[1000026 + 10];
long long kasumi(long long x, long long y) {
  long long ans = 1;
  for (; y > 0; y >>= 1, x = x * x % 1000000007)
    if (y & 1) ans = ans * x % 1000000007;
  return ans;
}
void rd() { cin >> n >> m; }
signed main() {
  rd();
  for (long long i = 1; i <= m + 2; i++) {
    y[i] = (y[i - 1] + kasumi(i, m)) % 1000000007;
  }
  jc[0] = fjc[0] = 1;
  for (long long i = 1; i <= m + 2; i++) {
    jc[i] = jc[i - 1] * i % 1000000007;
    fjc[i] = fjc[i - 1] * (1000000007 - i) % 1000000007;
  }
  a[0] = 1;
  for (long long i = 1; i <= m + 2; i++) a[i] = (n - i) * a[i - 1] % 1000000007;
  b[m + 3] = 1;
  for (long long i = m + 2; i >= 1; i--) b[i] = b[i + 1] * (n - i) % 1000000007;
  long long ans = 0;
  if (n <= m + 2) {
    cout << y[n] << "\n";
    return 0;
  }
  for (long long i = 1; i <= m + 2; i++) {
    ans += y[i] * a[i - 1] % 1000000007 * b[i + 1] % 1000000007 *
           kasumi(jc[i - 1], 1000000007 - 2) % 1000000007 *
           kasumi(fjc[-i + m + 2], 1000000007 - 2) % 1000000007;
    ans %= 1000000007;
  }
  cout << ans;
  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;
long long n, m;
long long y[1000026 + 10];
long long jc[1000026 + 10], fjc[1000026 + 10], a[1000026 + 10], b[1000026 + 10];
long long kasumi(long long x, long long y) {
  long long ans = 1;
  for (; y > 0; y >>= 1, x = x * x % 1000000007)
    if (y & 1) ans = ans * x % 1000000007;
  return ans;
}
void rd() { cin >> n >> m; }
signed main() {
  rd();
  for (long long i = 1; i <= m + 2; i++) {
    y[i] = (y[i - 1] + kasumi(i, m)) % 1000000007;
  }
  jc[0] = fjc[0] = 1;
  for (long long i = 1; i <= m + 2; i++) {
    jc[i] = jc[i - 1] * i % 1000000007;
    fjc[i] = fjc[i - 1] * (1000000007 - i) % 1000000007;
  }
  a[0] = 1;
  for (long long i = 1; i <= m + 2; i++) a[i] = (n - i) * a[i - 1] % 1000000007;
  b[m + 3] = 1;
  for (long long i = m + 2; i >= 1; i--) b[i] = b[i + 1] * (n - i) % 1000000007;
  long long ans = 0;
  if (n <= m + 2) {
    cout << y[n] << "\n";
    return 0;
  }
  for (long long i = 1; i <= m + 2; i++) {
    ans += y[i] * a[i - 1] % 1000000007 * b[i + 1] % 1000000007 *
           kasumi(jc[i - 1], 1000000007 - 2) % 1000000007 *
           kasumi(fjc[-i + m + 2], 1000000007 - 2) % 1000000007;
    ans %= 1000000007;
  }
  cout << ans;
  return 0;
}

```