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 long long MAXN = 1e6 + 50, Mod = 1e9 + 7;
long long n, K, ans = 0, Prime[MAXN], tot = 0, bk[MAXN], Pow[MAXN], Q[MAXN],
                H[MAXN], INV[MAXN];
struct Point {
  long long x, y;
} P[MAXN];
long long quickpower(long long x, long long y) {
  long long z = 1;
  while (y) {
    if (y & 1) z = 1ll * x * z % Mod;
    x = 1ll * x * x % Mod;
    y >>= 1;
  }
  return z;
}
long long inv(long long x) { return quickpower(x % Mod, Mod - 2); }
void GetPrime(long long N) {
  Pow[1] = 1;
  for (long long i = 2; i <= N; i++) {
    if (!bk[i]) Prime[++tot] = i, Pow[i] = quickpower(i, K);
    for (long long j = 1; j <= tot && Prime[j] * i <= N; j++) {
      bk[Prime[j] * i] = 1;
      Pow[Prime[j] * i] = 1ll * Pow[Prime[j]] * Pow[i] % Mod;
      if (i % Prime[j] == 0) break;
    }
  }
  return;
}
signed main() {
  cin >> n >> K;
  GetPrime(K + 2);
  long long s = 1;
  H[0] = 1, Q[0] = 1;
  for (long long i = 1; i <= K + 2; i++) {
    P[i].x = i;
    P[i].y = (P[i - 1].y + Pow[i]) % Mod;
    s = 1ll * s * ((n - i + Mod) % Mod) % Mod;
    Q[i] = 1ll * Q[i - 1] * i % Mod;
    H[i] = 1ll * H[i - 1] * (Mod - i) % Mod;
  }
  if (n <= K + 2) {
    printf("%d", P[n].y);
    return 0;
  }
  for (long long i = 1; i <= K + 2; i++) {
    long long t = inv(1ll * Q[i - 1] % Mod * H[K + 2 - i] % Mod);
    ans =
        ans + 1ll * s * inv((n - i + Mod) % Mod) % Mod * t % Mod * P[i].y % Mod,
    ans %= Mod;
  }
  cout << ans;
  return 0;
}