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;
inline void rd(long long &x) {
  x = 0;
  char ch = 0;
  long long w = 0;
  while (!isdigit(ch)) ch = getchar(), w |= ch == '-';
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  x = w ? -x : x;
}
long long n, k, ans, now;
long long a[1000005], f[1000005], g[1000005];
inline long long POW(long long a, long long b, long long ans = 1) {
  for (; b; b >>= 1, a = a * a % 1000000007)
    if (b & 1) ans = ans * a % 1000000007;
  return ans;
}
void solve() {
  if (n <= k + 2) return ans = a[n], void();
  long long now = 1;
  f[0] = g[0] = 1;
  for (long long i = 1; i <= k + 2; i++)
    now = now * (n - i) % 1000000007, f[i] = f[i - 1] * i % 1000000007,
    g[i] = -g[i - 1] * i % 1000000007;
  ;
  for (long long a1 = 1, a2 = 1, i = 1; i <= k + 2;
       ans = (ans + a[i++] * a1 % 1000000007 * POW(a2, 1000000007 - 2)) %
             1000000007,
                 a1 = a2 = 1)
    a1 = now * POW(n - i, 1000000007 - 2) % 1000000007,
    a2 = f[i - 1] * g[k + 2 - i] % 1000000007;
}
signed main() {
  cin >> n >> k;
  for (long long i = 1; i <= k + 2 and i <= n; i++)
    a[i] = (a[i - 1] + POW(i, k)) % 1000000007;
  solve();
  cout << (ans + 1000000007) % 1000000007;
}