#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long cnt = 0, f = 1;
  char ch = 0;
  while (!isdigit(ch)) {
    ch = getchar();
    if (ch == '-') f = -1;
  }
  while (isdigit(ch)) {
    cnt = cnt * 10 + ch - 48;
    ch = getchar();
  }
  return cnt * f;
}
long long a[2003000], n, k;
long long ans;
const long long mod = 1e9 + 7;
long long f[2004000], g[2000400];
long long ksm(long long a, long long b) {
  long long sum = 1;
  while (b) {
    if (b & 1) sum = sum * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return sum;
}
void solve() {
  long long now = 1;
  f[0] = g[0] = 1;
  for (long long i = 1; i <= k + 2; i++) {
    now = now * (n - i) % mod;
    f[i] = f[i - 1] * i % mod;
    g[i] = -g[i - 1] * i % mod;
  }
  for (long long i = 1; i <= k + 2; i++) {
    ans = (ans + a[i] * now % mod * ksm(n - i, mod - 2) % mod *
                     ksm(f[i - 1] * g[k + 2 - i] % mod, mod - 2) % mod) %
          mod;
  }
}
signed main() {
  n = read();
  k = read();
  for (long long i = 1; i <= n && i <= k + 2; i++) {
    a[i] = a[i - 1] + ksm(i, k);
    a[i] %= mod;
  }
  if (n <= k + 2) {
    cout << a[n];
    return 0;
  }
  solve();
  cout << (ans + mod) % mod;
  return 0;
}

### Prompt

In CPP, your task is to solve 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 read() {
  long long cnt = 0, f = 1;
  char ch = 0;
  while (!isdigit(ch)) {
    ch = getchar();
    if (ch == '-') f = -1;
  }
  while (isdigit(ch)) {
    cnt = cnt * 10 + ch - 48;
    ch = getchar();
  }
  return cnt * f;
}
long long a[2003000], n, k;
long long ans;
const long long mod = 1e9 + 7;
long long f[2004000], g[2000400];
long long ksm(long long a, long long b) {
  long long sum = 1;
  while (b) {
    if (b & 1) sum = sum * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return sum;
}
void solve() {
  long long now = 1;
  f[0] = g[0] = 1;
  for (long long i = 1; i <= k + 2; i++) {
    now = now * (n - i) % mod;
    f[i] = f[i - 1] * i % mod;
    g[i] = -g[i - 1] * i % mod;
  }
  for (long long i = 1; i <= k + 2; i++) {
    ans = (ans + a[i] * now % mod * ksm(n - i, mod - 2) % mod *
                     ksm(f[i - 1] * g[k + 2 - i] % mod, mod - 2) % mod) %
          mod;
  }
}
signed main() {
  n = read();
  k = read();
  for (long long i = 1; i <= n && i <= k + 2; i++) {
    a[i] = a[i - 1] + ksm(i, k);
    a[i] %= mod;
  }
  if (n <= k + 2) {
    cout << a[n];
    return 0;
  }
  solve();
  cout << (ans + mod) % mod;
  return 0;
}

```