#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1000005;
long long power(long long a, long long n) {
  long long res = 1, cur = a;
  while (n > 0) {
    if (n & 1) res = res * cur % MOD;
    cur = cur * cur % MOD;
    n /= 2;
  }
  return res;
}
int n, k;
long long fac[N], inv[N], p[N];
int main() {
  cin >> n >> k;
  fac[0] = inv[0] = 1;
  for (int i = 1; i < N; i++)
    fac[i] = fac[i - 1] * i % MOD, inv[i] = power(fac[i], MOD - 2);
  for (int i = 1; i <= k + 2; i++) p[i] = (p[i - 1] + power(i, k)) % MOD;
  long long ans = 0;
  if (n <= k + 2)
    ans = p[n];
  else {
    long long prods = 1;
    for (int i = 1; i <= k + 2; i++) prods = prods * (n - i) % MOD;
    for (int j = 1; j <= k + 2; j++) {
      long long d = inv[j - 1] * inv[k + 2 - j] % MOD;
      if ((k - j) & 1) d = (MOD - d) % MOD;
      ans += (prods * power(n - j, MOD - 2) % MOD) * (d * p[j] % MOD) % MOD;
      ans %= MOD;
    }
  }
  cout << ans << endl;
  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;
const int MOD = 1e9 + 7;
const int N = 1000005;
long long power(long long a, long long n) {
  long long res = 1, cur = a;
  while (n > 0) {
    if (n & 1) res = res * cur % MOD;
    cur = cur * cur % MOD;
    n /= 2;
  }
  return res;
}
int n, k;
long long fac[N], inv[N], p[N];
int main() {
  cin >> n >> k;
  fac[0] = inv[0] = 1;
  for (int i = 1; i < N; i++)
    fac[i] = fac[i - 1] * i % MOD, inv[i] = power(fac[i], MOD - 2);
  for (int i = 1; i <= k + 2; i++) p[i] = (p[i - 1] + power(i, k)) % MOD;
  long long ans = 0;
  if (n <= k + 2)
    ans = p[n];
  else {
    long long prods = 1;
    for (int i = 1; i <= k + 2; i++) prods = prods * (n - i) % MOD;
    for (int j = 1; j <= k + 2; j++) {
      long long d = inv[j - 1] * inv[k + 2 - j] % MOD;
      if ((k - j) & 1) d = (MOD - d) % MOD;
      ans += (prods * power(n - j, MOD - 2) % MOD) * (d * p[j] % MOD) % MOD;
      ans %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}

```