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>
const int MAXK = 1E6 + 10;
const long long MOD = 1E9 + 7;
long long y[MAXK];
long long modExp(long long e, long long n, long long m = MOD) {
  long long ret = 1;
  for (; n; n >>= 1, e = e * e % m)
    if (n & 1) ret = ret * e % MOD;
  return ret;
}
int main() {
  int n, K;
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= K + 1; ++i) y[i] = (y[i - 1] + modExp(i, K)) % MOD;
  if (n <= K + 1)
    printf("%d\n", (int)y[n]);
  else {
    long long num = n, den = 1;
    for (int i = 1; i <= K + 1; ++i) {
      num = num * (n - i) % MOD;
      den = den * (MOD - i) % MOD;
    }
    den = modExp(den, MOD - 2);
    long long ans = 0;
    for (int i = 0; i <= K + 1; ++i) {
      ans = (ans + num * modExp(n - i, MOD - 2) % MOD * den % MOD * y[i]) % MOD;
      den = den * modExp(i + 1, MOD - 2) % MOD * (MOD + i - K - 1) % MOD;
    }
    printf("%d", (int)ans);
  }
  return 0;
}