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 int MD = 1000000007;
const int MX = 1000005;
void add(int& a, int b) {
  a += b;
  if (a >= MD) a -= MD;
}
int mod_mult(long long a, long long b) { return (a * b) % MD; }
int exp(int a, int b) {
  int res = 1;
  while (b) {
    if (b % 2 == 1) res = mod_mult(res, a);
    a = mod_mult(a, a);
    b /= 2;
  }
  return res;
}
int inv(int a) { return exp(a, MD - 2); }
int fact[MX];
int inv_fact[MX];
int f(int n, int i) {
  int tmp = mod_mult(inv_fact[i], inv_fact[n - i - 1]);
  if ((n - i - 1) % 2 == 1) tmp = (MD - tmp) % MD;
  return tmp;
}
int val[MX];
int lagrange(int n, int x) {
  if (x < n) return val[x];
  int M = 1;
  for (int i = 0; i < n; i++) {
    M = mod_mult(M, x - i);
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    int tmp = mod_mult(M, inv(x - i));
    tmp = mod_mult(tmp, val[i]);
    tmp = mod_mult(tmp, f(n, i));
    add(res, tmp);
  }
  return res;
}
int main() {
  int n, k;
  ignore = scanf("%d %d", &n, &k);
  fact[0] = 1;
  for (int i = 1; i < MX; i++) {
    fact[i] = mod_mult(fact[i - 1], i);
  }
  inv_fact[MX - 1] = inv(fact[MX - 1]);
  for (int i = MX - 2; i >= 0; i--) {
    inv_fact[i] = mod_mult(inv_fact[i + 1], i + 1);
  }
  for (int i = 1; i <= k + 1; i++) {
    val[i] = val[i - 1];
    add(val[i], exp(i, k));
  }
  printf("%d\n", lagrange(k + 2, n));
}