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 Mod = 1000000000 + 7;
const int MAXK = 1000000;
int power(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = 1LL * ret * x % Mod;
    x = 1LL * x * x % Mod;
    k >>= 1;
  }
  return ret;
}
int n, k, ans;
int f[MAXK + 10];
void init() {
  cin >> n >> k;
  if (n <= k + 10) {
    for (int i = 1; i <= n; i++) ans = (power(i, k) + ans) % Mod;
    cout << ans;
  } else {
    for (int i = 1; i <= k + 2; i++) f[i] = (f[i - 1] + power(i, k)) % Mod;
    int s = 1, m = 1;
    for (int j = 2; j <= k + 2; j++) s = 1LL * s * (n - j) % Mod;
    for (int j = 2; j <= k + 2; j++) m = 1LL * m * ((1 - j) + Mod) % Mod;
    int l = -(k + 1), r = 1;
    for (int i = 1; i <= k + 2; i++) {
      ans = (1LL * f[i] * s % Mod * power(m, Mod - 2) % Mod + ans) % Mod;
      s = 1LL * s * (n - i) % Mod * power(n - (i + 1), Mod - 2) % Mod;
      m = 1LL * m * r % Mod * power(l + Mod, Mod - 2) % Mod;
      l++, r++;
    }
    cout << ans;
  }
  return;
}
int main() {
  init();
  return 0;
}