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 long long P = 1e9 + 7;
const int N = 1e6 + 50;
long long pwr(long long a, long long k) {
  long long res = 1;
  for (a %= P; k; k >>= 1, a = a * a % P) {
    if (k & 1) res = res * a % P;
  }
  return res;
}
long long inv(long long x) { return pwr(x, P - 2); }
long long f(long long n, long long k) {
  static long long up[N], down[N];
  up[0] = 1;
  for (int i = 1; i <= (k + 1); ++i) up[i] = up[i - 1] * i % P;
  down[0] = 1;
  for (int i = 1; i <= (k + 1); ++i) down[i] = down[i - 1] * (-i + P) % P;
  long long prod = 1;
  for (int i = 0; i <= (k + 1); ++i) prod = prod * (n - i) % P;
  ;
  long long cur = 0, ans = 0;
  for (int x = 0; x <= (k + 1); ++x) {
    ;
    if (x) cur += pwr(x, k);
    cur %= P;
    ;
    if (x == n) {
      ans = cur;
      break;
    }
    long long u = prod * inv(n - x) % P;
    ;
    long long d = inv(up[x] * down[k + 1 - x] % P);
    ;
    ;
    ;
    ans += u * d % P * cur % P;
    ans %= P;
    ;
  }
  return ans;
}
int main(int argc, char *argv[]) {
  long long n, k;
  cin >> n >> k;
  cout << f(n, k) << endl;
  return 0;
}