#include <bits/stdc++.h>
std::pair<int64_t, int64_t> ReadData(std::istream& in_stream = std::cin);
int64_t Solution(int64_t n, int64_t k);
void WriteData(int64_t result, std::ostream& out_stream = std::cout);
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  auto input = ReadData();
  auto result = Solution(input.first, input.second);
  WriteData(result);
  return 0;
}
int64_t NaiveSolution(int64_t n, int64_t k);
int64_t CalculateUseInterpolation(int64_t n, int64_t step);
int64_t Solution(int64_t n, int64_t k) {
  int64_t result;
  if (n <= k + 2) {
    result = NaiveSolution(n, k);
  } else {
    result = CalculateUseInterpolation(n, k);
  }
  return result;
}
int64_t BinaryPow(int64_t a, int64_t n, int64_t modulo);
int64_t NaiveSolution(int64_t n, int64_t k) {
  int64_t mod = 1000 * 1000 * 1000 + 7;
  int64_t result = 0;
  for (int64_t idx = 1; idx <= n; ++idx) {
    result = (result + BinaryPow(idx, k, mod)) % mod;
  }
  return result;
}
int64_t CalculateUseInterpolation(int64_t n, int64_t step) {
  int64_t result = 0;
  int64_t sum = 1;
  int64_t mod = 1000 * 1000 * 1000 + 7;
  int64_t p = static_cast<int64_t>(1);
  for (int64_t idx = 2; idx <= step + 2; ++idx) {
    int64_t numerator = (n - idx + mod) % mod;
    int64_t denumerator = (1 - idx + mod) % mod;
    int64_t current_fraction = BinaryPow(denumerator, mod - 2, mod);
    current_fraction = (current_fraction * numerator) % mod;
    p = (p * current_fraction) % mod;
  }
  for (int64_t i = 1; i <= step + 3; ++i) {
    result = ((p * sum) % mod + result) % mod;
    sum = (sum + BinaryPow((i + 1), step, mod)) % mod;
    int64_t numerator = ((n - i + mod) * (i - (step + 2) + mod)) % mod;
    int64_t denumirator = ((n - (i + 1) + mod) % mod * i) % mod;
    denumirator = BinaryPow(denumirator, mod - 2, mod);
    int64_t q = (numerator * denumirator) % mod;
    p = (p * q) % mod;
  }
  return result;
}
int64_t BinaryPow(int64_t a, int64_t n, int64_t modulo) {
  int64_t result = 1;
  while (n) {
    if (n % 2 == 1) {
      --n;
      result = (result * a) % modulo;
    } else {
      n /= 2;
      a = (a * a) % modulo;
    }
  }
  return result;
}
std::pair<int64_t, int64_t> ReadData(std::istream& in_stream) {
  int64_t n, k;
  in_stream >> n >> k;
  return {n, k};
}
void WriteData(int64_t result, std::ostream& out_stream) {
  out_stream << result << "\n";
}

### Prompt

Create a solution in cpp for the following 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

### Response

```cpp
#include <bits/stdc++.h>
std::pair<int64_t, int64_t> ReadData(std::istream& in_stream = std::cin);
int64_t Solution(int64_t n, int64_t k);
void WriteData(int64_t result, std::ostream& out_stream = std::cout);
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  auto input = ReadData();
  auto result = Solution(input.first, input.second);
  WriteData(result);
  return 0;
}
int64_t NaiveSolution(int64_t n, int64_t k);
int64_t CalculateUseInterpolation(int64_t n, int64_t step);
int64_t Solution(int64_t n, int64_t k) {
  int64_t result;
  if (n <= k + 2) {
    result = NaiveSolution(n, k);
  } else {
    result = CalculateUseInterpolation(n, k);
  }
  return result;
}
int64_t BinaryPow(int64_t a, int64_t n, int64_t modulo);
int64_t NaiveSolution(int64_t n, int64_t k) {
  int64_t mod = 1000 * 1000 * 1000 + 7;
  int64_t result = 0;
  for (int64_t idx = 1; idx <= n; ++idx) {
    result = (result + BinaryPow(idx, k, mod)) % mod;
  }
  return result;
}
int64_t CalculateUseInterpolation(int64_t n, int64_t step) {
  int64_t result = 0;
  int64_t sum = 1;
  int64_t mod = 1000 * 1000 * 1000 + 7;
  int64_t p = static_cast<int64_t>(1);
  for (int64_t idx = 2; idx <= step + 2; ++idx) {
    int64_t numerator = (n - idx + mod) % mod;
    int64_t denumerator = (1 - idx + mod) % mod;
    int64_t current_fraction = BinaryPow(denumerator, mod - 2, mod);
    current_fraction = (current_fraction * numerator) % mod;
    p = (p * current_fraction) % mod;
  }
  for (int64_t i = 1; i <= step + 3; ++i) {
    result = ((p * sum) % mod + result) % mod;
    sum = (sum + BinaryPow((i + 1), step, mod)) % mod;
    int64_t numerator = ((n - i + mod) * (i - (step + 2) + mod)) % mod;
    int64_t denumirator = ((n - (i + 1) + mod) % mod * i) % mod;
    denumirator = BinaryPow(denumirator, mod - 2, mod);
    int64_t q = (numerator * denumirator) % mod;
    p = (p * q) % mod;
  }
  return result;
}
int64_t BinaryPow(int64_t a, int64_t n, int64_t modulo) {
  int64_t result = 1;
  while (n) {
    if (n % 2 == 1) {
      --n;
      result = (result * a) % modulo;
    } else {
      n /= 2;
      a = (a * a) % modulo;
    }
  }
  return result;
}
std::pair<int64_t, int64_t> ReadData(std::istream& in_stream) {
  int64_t n, k;
  in_stream >> n >> k;
  return {n, k};
}
void WriteData(int64_t result, std::ostream& out_stream) {
  out_stream << result << "\n";
}

```