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 P = 1e9 + 7;
const int N = 1e6 + 10;
void update(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
int fpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % P)
    if (b & 1) ret = 1ll * ret * a % P;
  return ret;
}
int pre[N], suf[N], ifac[N], inv[N];
int main() {
  int n, K;
  scanf("%d%d", &n, &K);
  if (K == 0) {
    printf("%d\n", n);
    return 0;
  }
  ifac[0] = 1, inv[1] = 1, ifac[1] = 1;
  for (int i = 2; i <= K + 2; i++) {
    inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
    ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
  }
  pre[0] = 1;
  for (int i = 1; i <= K + 2; i++)
    pre[i] = 1ll * pre[i - 1] * (((n - i) % P + P) % P) % P;
  suf[K + 3] = 1;
  for (int i = K + 2; i >= 0; i--)
    suf[i] = 1ll * suf[i + 1] * (((n - i) % P + P) % P) % P;
  int yi = 0, ans = 0;
  for (int i = 1; i <= K + 2; i++) {
    update(yi, fpow(i, K));
    long long tmp = 1ll * yi * ifac[i - 1] % P * ifac[K + 2 - i] % P *
                    pre[i - 1] % P * suf[i + 1] % P;
    if ((K + 2 - i) % 2 == 0)
      update(ans, tmp);
    else
      update(ans, P - tmp);
  }
  printf("%d\n", ans);
  return 0;
}