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 maxk = 1000000 + 10;
long long n, k;
long long qpow(long long m, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = (res * m) % mod;
    m = (m * m) % mod;
    n = n >> 1;
  }
  return res;
}
long long fac[maxk], y[maxk];
long long Largrange() {
  fac[0] = fac[1] = 1, y[1] = 1;
  for (int i = 2; i <= k + 2; i++) fac[i] = fac[i - 1] * i % mod;
  for (int i = 2; i <= k + 2; i++) y[i] = (y[i - 1] + qpow(i, k, mod)) % mod;
  if (n <= k + 2) return y[n];
  long long ans = 0, prod = 1, sig;
  for (long long i = n - k - 2; i <= n - 1; i++) prod = prod * i % mod;
  for (long long i = 1; i <= k + 2; i++) {
    long long fz = prod * qpow(n - i, mod - 2, mod) % mod;
    long long fm = qpow(fac[i - 1] * fac[k + 2 - i] % mod, mod - 2, mod);
    if ((k + 2 - i) % 2 == 0)
      sig = 1;
    else
      sig = -1;
    ans = (ans + sig * y[i] * fz % mod * fm % mod + 2 * mod) % mod;
  }
  return ans;
}
int main() {
  scanf("%lld%lld", &n, &k);
  printf("%lld\n", Largrange());
  return 0;
}