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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int N = 1e6 + 5;
long long F[N], fac[N], D[N];
long long ksm(long long a, int b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = (ret * a) % mod;
    b >>= 1, a = a * a % mod;
  }
  return ret;
}
long long inv(long long x) {
  return x == 1 ? 1 : (mod - mod / x) * inv(mod % x) % mod;
}
int n, k;
long long fun(long long x) {
  if (x <= k + 1) return F[x];
  long long p = 1, ret = 0;
  for (int i = 0; i <= k + 1; i++) p = p * (x - i) % mod;
  for (int i = 1; i <= k + 1; i++)
    ret = (ret + D[i] * p % mod * inv(x - i)) % mod;
  return ret;
}
void init() {
  fac[0] = 1;
  for (int i = 1; i <= k + 1; i++) {
    fac[i] = fac[i - 1] * i % mod;
    F[i] = F[i - 1] + ksm(i, k);
    if (F[i] >= mod) F[i] -= mod;
  }
  for (int i = 0; i <= k + 1; i++)
    D[i] = F[i] *
           inv(fac[i] * fac[k + 1 - i] % mod * ((k + i - 1) & 1 ? mod - 1 : 1) %
               mod) %
           mod;
}
void solve() {
  cin >> n >> k;
  init();
  cout << fun(n) << '\n';
}
int main() {
  solve();
  return 0;
}