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 M = 1e9 + 7;
long long add(long long x, long long y) {
  x += y;
  if (x > M) x -= M;
  return x;
}
long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) x += M;
  return x;
}
long long mul(long long x, long long y) { return (x * y) % M; }
long long power(long long a, long long x) {
  long long rt = 1;
  if (a < 0) a += M;
  a %= M;
  while (x > 0) {
    if (x & 1) rt = mul(rt, a);
    x >>= 1;
    a = mul(a, a);
  }
  return rt;
}
long long inv(long long x) {
  if (x < 0) x += M;
  x %= M;
  ;
  return power(x, M - 2);
}
long long inter(vector<long long>& ff, long long x) {
  long long ls = ff.size();
  long long num = 1, den = 1;
  long long i;
  long long ch = 1;
  for (i = 0; i < ls; i++) {
    num = mul(num, x - i + M);
    if ((x - i) != 0) ch = mul(ch, x - i + M);
    if (i != 0) den = mul(den, M - i);
  };
  long long ans = 0;
  long long deni = inv(den);
  for (i = 0; i < ls; i++) {
    long long nnum;
    if (num == 0) {
      nnum = (x == i ? ch : 0);
    } else
      nnum = mul(num, inv(x - i + M));
    if (i != 0) {
      deni = mul(deni, inv(i));
      deni = mul(deni, (i - ls + M));
    }
    long long aa = mul(ff[i], mul(nnum, deni));
    ;
    ans = add(ans, aa);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(25);
  long long n, k, a, b, c, d, i, j;
  cin >> n >> k;
  vector<long long> v;
  long long pr = 0;
  for (i = 0; i <= k + 1; i++) {
    pr = add(pr, power(i, k));
    v.push_back(pr);
  }
  if (k == 0) {
    cout << n;
    return 0;
  }
  cout << inter(v, n);
  return 0;
}