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 = 1e9 + 7;
inline int fsp(int x, int p = Mod - 2) {
  int res = 1;
  while (p) {
    if (p & 1) res = 1ll * res * x % Mod;
    x = 1ll * x * x % Mod, p >>= 1;
  }
  return res;
}
int n, m, f[2006006], fac[2006006], ifac[2006006];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m + 1; ++i) f[i] = (f[i - 1] + fsp(i, m)) % Mod;
  if (n <= m + 1) return cout << f[n] << endl, 0;
  for (int i = fac[0] = 1; i <= m + 1; ++i) fac[i] = 1ll * fac[i - 1] * i % Mod;
  ifac[m + 1] = fsp(fac[m + 1]);
  for (int i = m + 1; i >= 1; --i) ifac[i - 1] = 1ll * ifac[i] * i % Mod;
  long long ans = 0;
  for (int i = 1; i <= m + 1; ++i) {
    int tmp = f[i], t;
    tmp = 1ll * tmp * fsp(n - i) % Mod;
    tmp = 1ll * tmp * ifac[i] % Mod;
    tmp = 1ll * tmp * ifac[t = ((m + 1) - i)] % Mod;
    if (t & 1) tmp = Mod - tmp;
    ans = (ans + tmp) % Mod;
  }
  for (int i = 0; i <= m + 1; ++i) ans = ans * (n - i) % Mod;
  cout << ans << endl;
  return 0;
}