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;
inline long long read() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ans = (ans << 1) + (ans << 3) + c - '0';
    c = getchar();
  }
  return ans * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x / 10) write(x / 10);
  putchar((char)(x % 10) + '0');
}
template <typename T>
inline T Abs(T a) {
  return a > 0 ? a : -a;
};
template <typename T, typename TT>
inline T Min(T a, TT b) {
  return a > b ? b : a;
}
template <typename T, typename TT>
inline T Max(T a, TT b) {
  return a > b ? a : b;
}
const long long N = 1e6 + 5, mod = 1e9 + 7;
long long n, k, jc[N], inv[N], sum[N], pre[N], suc[N], ans;
inline long long q_pow(long long a, long long b);
signed main() {
  n = read();
  k = read();
  jc[0] = 1;
  for (long long i = 1; i <= k + 2; ++i) jc[i] = jc[i - 1] * i % mod;
  inv[k + 2] = q_pow(jc[k + 2], mod - 2);
  for (long long i = k + 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
  for (long long i = 1; i <= k + 2; ++i)
    sum[i] = (sum[i - 1] + q_pow(i, k)) % mod;
  pre[0] = 1;
  for (long long i = 1; i <= k + 2; ++i) pre[i] = pre[i - 1] * (n - i) % mod;
  suc[k + 3] = 1;
  for (long long i = k + 2; i >= 1; --i) suc[i] = suc[i + 1] * (n - i) % mod;
  for (long long i = 1; i <= k + 2; ++i) {
    long long tmp = sum[i];
    tmp = tmp * inv[i - 1] % mod * inv[k + 2 - i] % mod;
    tmp = tmp * pre[i - 1] % mod * suc[i + 1] % mod;
    if (!((k - i) & 1))
      ans = (ans + tmp) % mod;
    else
      ans = (ans - tmp + mod) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}
inline long long q_pow(long long a, long long b) {
  long long c = 1;
  while (b) {
    if (b & 1) c = a * c % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return c;
}