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 int mo = 1e9 + 7;
const int N = 1e6 + 500;
long long powm(long long a, long long b) {
  a %= mo;
  long long r = 1;
  for (; b; b >>= 1, a = a * a % mo)
    if (b & 1) r = r * a % mo;
  return r;
}
void ntr(int &x) { x = x >= mo ? x - mo : (x < 0 ? x + mo : x); }
void inc(int &x, int y) { x += y, ntr(x); }
int L[N], R[N], inv[N], n, K;
void init() {
  L[0] = 1;
  for (int i = 1; i <= K + 1; i++) L[i] = 1ll * L[i - 1] * (n - i + 1) % mo;
  R[K + 1] = 1;
  for (int i = K; i >= 0; i--) R[i] = 1ll * R[i + 1] * (n - i - 1) % mo;
  inv[1] = 1;
  for (int i = 2; i <= K + 1; i++)
    inv[i] = 1ll * (mo - mo / i) * inv[mo % i] % mo;
  inv[0] = 1;
  for (int i = 1; i <= K + 1; i++) inv[i] = 1ll * inv[i - 1] * inv[i] % mo;
}
int main() {
  scanf("%d%d", &n, &K);
  if (K == 0) return printf("%d\n", n), 0;
  if (n <= K + 1) {
    int ans = 0;
    for (int i = 1; i <= n; i++) inc(ans, powm(i, K));
    return printf("%d\n", ans), 0;
  }
  init();
  int vl = 0, ans = 0;
  for (int i = 0; i <= K + 1; i++) {
    inc(vl, powm(i, K));
    long long f = ((i ^ K) & 1) ? 1 : -1;
    inc(ans, f * vl % mo * L[i] % mo * R[i] % mo * inv[i] % mo *
                 inv[K + 1 - i] % mo);
  }
  return printf("%d\n", ans), 0;
}