#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long po(long long a, long long b) {
  if (b == 0) return 1 % mod;
  long long y = po(a, b / 2);
  y = y * y % mod;
  if (b % 2 == 1) y = y * a % mod;
  return y;
}
long long iv[1000007], ifac[1000007];
void pre() {
  ifac[0] = 1;
  iv[1] = ifac[1] = 1;
  for (long long i = (long long)2; i != (long long)1000007; i = i + 1) {
    iv[i] = mod - (mod / i) * iv[mod % i] % mod;
    ifac[i] = ifac[i - 1] * iv[i] % mod;
  }
}
long long sol(const vector<long long> &y, long long x) {
  int d = (int)y.size() - 1;
  long long pre[d + 1], suff[d + 2];
  pre[0] = suff[d + 1] = 1;
  for (long long i = (long long)1; i != (long long)d + 1; i = i + 1) {
    pre[i] = pre[i - 1] * (x - i + 1) % mod;
    ;
  }
  for (long long i = (long long)d; i != (long long)-1; i = i + -1) {
    suff[i] = suff[i + 1] * (x - i) % mod;
    ;
  }
  long long ans = 0;
  for (long long i = (long long)1; i != (long long)d + 1; i = i + 1) {
    ;
    ans += 1ll * ((d - i) & 1 ? -1 : 1) * y[i] % mod *
           (pre[i] * suff[i + 1] % mod) % mod * (ifac[i] * ifac[d - i] % mod) %
           mod;
    ans %= mod;
    ;
  }
  ans = (ans + mod) % mod;
  return ans;
}
void solve() {
  pre();
  long long n, k;
  cin >> n >> k;
  vector<long long> y;
  long long sm = 0;
  y.push_back(sm);
  for (long long i = (long long)1; i != (long long)k + 2; i = i + 1) {
    sm = (sm + po(i, k)) % mod;
    ;
    y.push_back(sm);
  }
  cout << sol(y, n) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

### 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;
const long long mod = 1e9 + 7;
long long po(long long a, long long b) {
  if (b == 0) return 1 % mod;
  long long y = po(a, b / 2);
  y = y * y % mod;
  if (b % 2 == 1) y = y * a % mod;
  return y;
}
long long iv[1000007], ifac[1000007];
void pre() {
  ifac[0] = 1;
  iv[1] = ifac[1] = 1;
  for (long long i = (long long)2; i != (long long)1000007; i = i + 1) {
    iv[i] = mod - (mod / i) * iv[mod % i] % mod;
    ifac[i] = ifac[i - 1] * iv[i] % mod;
  }
}
long long sol(const vector<long long> &y, long long x) {
  int d = (int)y.size() - 1;
  long long pre[d + 1], suff[d + 2];
  pre[0] = suff[d + 1] = 1;
  for (long long i = (long long)1; i != (long long)d + 1; i = i + 1) {
    pre[i] = pre[i - 1] * (x - i + 1) % mod;
    ;
  }
  for (long long i = (long long)d; i != (long long)-1; i = i + -1) {
    suff[i] = suff[i + 1] * (x - i) % mod;
    ;
  }
  long long ans = 0;
  for (long long i = (long long)1; i != (long long)d + 1; i = i + 1) {
    ;
    ans += 1ll * ((d - i) & 1 ? -1 : 1) * y[i] % mod *
           (pre[i] * suff[i + 1] % mod) % mod * (ifac[i] * ifac[d - i] % mod) %
           mod;
    ans %= mod;
    ;
  }
  ans = (ans + mod) % mod;
  return ans;
}
void solve() {
  pre();
  long long n, k;
  cin >> n >> k;
  vector<long long> y;
  long long sm = 0;
  y.push_back(sm);
  for (long long i = (long long)1; i != (long long)k + 2; i = i + 1) {
    sm = (sm + po(i, k)) % mod;
    ;
    y.push_back(sm);
  }
  cout << sol(y, n) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

```