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>
inline int add(int x, int y) {
  return (x += y) >= 1000000007 ? x - 1000000007 : x;
}
inline int mul(int x, int y) { return (long long)x * y % 1000000007; }
inline int power(int x, int y) {
  int ans = 1;
  for (; y; y >>= 1) {
    if (y & 1) ans = mul(ans, x);
    x = mul(x, x);
  }
  return ans;
}
int n, k;
int pre[1000005], suf[1000005], fac[1000005];
int main() {
  scanf("%d%d", &n, &k);
  if (n <= k + 2) {
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = add(ans, power(i, k));
    printf("%d\n", ans);
    return 0;
  }
  pre[0] = 1;
  for (int i = 1; i <= k + 2; ++i) pre[i] = mul(pre[i - 1], n - i);
  suf[k + 3] = 1;
  for (int i = k + 2; i; --i) suf[i] = mul(suf[i + 1], n - i);
  fac[0] = 1;
  for (int i = 1; i <= k + 2; ++i) fac[i] = mul(fac[i - 1], i);
  int now = 0, ans = 0;
  for (int i = 1; i <= k + 2; ++i) {
    now = add(now, power(i, k));
    int x = mul(fac[i - 1], fac[k + 2 - i]);
    ans =
        add(ans, mul(mul(now, mul(pre[i - 1], suf[i + 1])),
                     power((k - i) & 1 ? 1000000007 - x : x, 1000000007 - 2)));
  }
  printf("%d\n", ans);
  return 0;
}