#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
long long int fpow(long long int p, long long int q) {
  long long int ret = 1;
  for (; q; q >>= 1) {
    if (q & 1) {
      ret = ret * p % mod;
    }
    p = p * p % mod;
  }
  return ret;
}
long long int pre[1000010];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + 3; i++) {
    pre[i] = fpow(i, k);
  }
  for (int i = 2; i <= k + 3; i++) {
    pre[i] = (pre[i] + pre[i - 1]) % mod;
  }
  if (n <= k + 3) {
    cout << pre[n] << endl;
  } else {
    long long int sorat = 1;
    for (int i = 1; i <= k + 2; i++) {
      sorat = (long long int)sorat * (n - i) % mod;
    }
    long long int makhraj = 1;
    for (int i = 1; i <= k + 1; i++) {
      makhraj = (long long int)makhraj * i % mod;
    }
    long long int br = 1;
    if ((k + 1) % 2 != 0) {
      br = -1;
    }
    long long int res = 0;
    for (int i = 1; i <= k + 2; i++) {
      res += (sorat * pre[i] % mod * fpow(n - i, mod - 2) % mod *
              fpow(makhraj, mod - 2) * br % mod);
      if (res < 0) {
        res += mod;
      }
      makhraj = makhraj * (i) % mod * fpow(k + 2 - i, mod - 2) % mod;
      br = -br;
    }
    cout << (res + mod) % mod << endl;
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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>
using namespace std;
const int mod = 1000000007;
long long int fpow(long long int p, long long int q) {
  long long int ret = 1;
  for (; q; q >>= 1) {
    if (q & 1) {
      ret = ret * p % mod;
    }
    p = p * p % mod;
  }
  return ret;
}
long long int pre[1000010];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k + 3; i++) {
    pre[i] = fpow(i, k);
  }
  for (int i = 2; i <= k + 3; i++) {
    pre[i] = (pre[i] + pre[i - 1]) % mod;
  }
  if (n <= k + 3) {
    cout << pre[n] << endl;
  } else {
    long long int sorat = 1;
    for (int i = 1; i <= k + 2; i++) {
      sorat = (long long int)sorat * (n - i) % mod;
    }
    long long int makhraj = 1;
    for (int i = 1; i <= k + 1; i++) {
      makhraj = (long long int)makhraj * i % mod;
    }
    long long int br = 1;
    if ((k + 1) % 2 != 0) {
      br = -1;
    }
    long long int res = 0;
    for (int i = 1; i <= k + 2; i++) {
      res += (sorat * pre[i] % mod * fpow(n - i, mod - 2) % mod *
              fpow(makhraj, mod - 2) * br % mod);
      if (res < 0) {
        res += mod;
      }
      makhraj = makhraj * (i) % mod * fpow(k + 2 - i, mod - 2) % mod;
      br = -br;
    }
    cout << (res + mod) % mod << endl;
  }
  return 0;
}

```