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;
long long n, k, ans, now;
long long a[1000005], f[1000005], g[1000005];
inline long long POW(long long a, long long b = 1000000007 - 2,
                     long long ans = 1) {
  for (; b; b >>= 1, a = a * a % 1000000007)
    if (b & 1) ans = ans * a % 1000000007;
  return ans;
}
void solve() {
  now = 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 i = 1; i <= k + 2; i++)
    ans = (ans + a[i] * now % 1000000007 * POW(n - i) % 1000000007 *
                     POW(f[i - 1] * g[k + 2 - i] % 1000000007)) %
          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;
  if (n <= k + 2) return cout << a[n], 0;
  solve();
  cout << (ans + 1000000007) % 1000000007;
}