#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100, MOD = 1e9 + 7, TOF = 10;
int add(long long a, int b) { return (a + b) % MOD; }
int mul(long long a, int b) { return a * b % MOD; }
void sadd(int &a, int b) { a = add(a, b); }
void smul(int &a, int b) { a = mul(a, b); }
int bp(int a, int b) {
  if (b == 0) return 1;
  int x = bp(a, b / 2);
  smul(x, x);
  return b & 1 ? mul(x, a) : x;
}
int inv(int a) { return bp(a, MOD - 2); }
int y[N], fact[N];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + TOF; i++) y[i] = add(bp(i, k), y[i - 1]);
  if (n <= k + TOF) {
    cout << y[n] << "\n";
    return 0;
  }
  fact[0] = 1;
  for (int i = 1; i < N; i++) fact[i] = mul(i, fact[i - 1]);
  int top = 1;
  for (int i = 1; i <= k + TOF; i++) smul(top, n - i);
  int ans = 0;
  for (int i = 1; i <= k + TOF; i++) {
    int cur = y[i];
    smul(cur, mul(top, inv(n - i)));
    int dn = mul(fact[i - 1], fact[k + TOF - i]);
    if ((k + TOF - i) & 1) dn = (MOD - dn) % MOD;
    smul(cur, inv(dn));
    sadd(ans, cur);
  }
  cout << ans << "\n";
}

### 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 N = 1e6 + 100, MOD = 1e9 + 7, TOF = 10;
int add(long long a, int b) { return (a + b) % MOD; }
int mul(long long a, int b) { return a * b % MOD; }
void sadd(int &a, int b) { a = add(a, b); }
void smul(int &a, int b) { a = mul(a, b); }
int bp(int a, int b) {
  if (b == 0) return 1;
  int x = bp(a, b / 2);
  smul(x, x);
  return b & 1 ? mul(x, a) : x;
}
int inv(int a) { return bp(a, MOD - 2); }
int y[N], fact[N];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + TOF; i++) y[i] = add(bp(i, k), y[i - 1]);
  if (n <= k + TOF) {
    cout << y[n] << "\n";
    return 0;
  }
  fact[0] = 1;
  for (int i = 1; i < N; i++) fact[i] = mul(i, fact[i - 1]);
  int top = 1;
  for (int i = 1; i <= k + TOF; i++) smul(top, n - i);
  int ans = 0;
  for (int i = 1; i <= k + TOF; i++) {
    int cur = y[i];
    smul(cur, mul(top, inv(n - i)));
    int dn = mul(fact[i - 1], fact[k + TOF - i]);
    if ((k + TOF - i) & 1) dn = (MOD - dn) % MOD;
    smul(cur, inv(dn));
    sadd(ans, cur);
  }
  cout << ans << "\n";
}

```