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 int read() {
  int sum = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  if (f) return -sum;
  return sum;
}
const int mod = 1000000007;
const int N = 1000005;
int n, m, k;
long long ny[N], f[N], ans;
inline long long quick(long long a, long long b) {
  long long r = 1, base = a;
  while (b) {
    if (b & 1) r = r * base % mod;
    base = base * base % mod;
    b >>= 1;
  }
  return r;
}
int main() {
  int i;
  long long u, t;
  n = read();
  k = read();
  m = k + 1;
  for (i = 1; i <= m; i++) f[i] = (f[i - 1] + quick(i, k)) % mod;
  if (n <= m) {
    printf("%d", f[n]);
    return 0;
  }
  for (u = 1, i = 2; i <= m; i++) u = u * i % mod;
  for (ny[m] = quick(u, mod - 2), ny[0] = 1, i = m; i >= 2; i--)
    ny[i - 1] = ny[i] * i % mod;
  for (t = 1, i = 0; i <= m; i++) t = t * (n - i) % mod;
  for (i = 0; i <= m; i++) {
    u = quick(n - i, mod - 2);
    if ((m - i) & 1)
      ans -= (t * f[i] % mod * u % mod * ny[m - i] % mod * ny[i] % mod);
    else
      ans += (t * f[i] % mod * u % mod * ny[m - i] % mod * ny[i] % mod);
    ans %= mod;
  }
  cout << (ans + mod) % mod;
  return 0;
}