Problem: Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation: 

F1 = 1, F2 = 2, Fi = Fi - 1 + Fi - 2 (i > 2).

We'll define a new number sequence Ai(k) by the formula: 

Ai(k) = Fi × ik (i ≥ 1).

In this problem, your task is to calculate the following sum: A1(k) + A2(k) + ... + An(k). The answer can be very large, so print it modulo 1000000007 (109 + 7).

Input

The first line contains two space-separated integers n, k (1 ≤ n ≤ 1017; 1 ≤ k ≤ 40).

Output

Print a single integer — the sum of the first n elements of the sequence Ai(k) modulo 1000000007 (109 + 7).

Examples

Input

1 1


Output

1


Input

4 1


Output

34


Input

5 2


Output

316


Input

7 4


Output

73825

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long int myRand(long long int B) { return (unsigned long long)rng() % B; }
constexpr long long int mod = 1e9 + 7;
long long int mod_pow(long long int a, long long int b) {
  a %= mod;
  if (b == 0) return 1;
  if (b == 1) return a;
  long long int res = mod_pow(a, b / 2) % mod;
  res *= res;
  res %= mod;
  if (b % 2) res *= a;
  return res % mod;
}
struct perm {
 private:
  int sz;
  vector<long long int> p, invp;

 public:
  perm(int n) {
    sz = n + 1;
    p.resize(sz), invp.resize(sz);
    p[0] = 1;
    for (int i = 1; i <= sz - 1; i++) {
      p[i] = p[i - 1] * i % mod;
    }
    invp[sz - 1] = mod_pow(p[sz - 1], mod - 2);
    for (int i = sz - 2; i >= 0; i--) {
      invp[i] = invp[i + 1] * (i + 1) % mod;
    }
  }
  long long int comb(long long int x, long long int y) {
    if (x < y || y < 0) return 0;
    return (p[x] * invp[x - y] % mod) * invp[y] % mod;
  }
};
perm p(1 << 20);
template <class T>
struct Mat {
  vector<vector<T>> A;
  Mat() {}
  Mat(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}
  Mat(size_t n) : A(n, vector<T>(n, 0)){};
  size_t height() const { return A.size(); }
  size_t width() const { return A[0].size(); }
  inline const vector<T> &operator[](int k) const { return A.at(k); }
  inline vector<T> &operator[](int k) { return A.at(k); }
  static Mat I(size_t n) {
    Mat mat(n);
    for (int i = 0; i < n; i++) {
      mat[i][i] = 1;
    }
    return mat;
  }
  Mat &operator+=(const Mat &B) {
    size_t n = height(), m = width();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        (*this)[i][j] = ((*this)[i][j] + B[i][j]) % mod;
      }
    }
    return (*this);
  }
  Mat &operator-=(const Mat &B) {
    size_t n = height(), m = width();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        (*this)[i][j] = ((*this)[i][j] - B[i][j]) % mod;
        if ((*this)[i][j] < 0) (*this)[i][j] += mod;
      }
    }
    return (*this);
  }
  Mat &operator*=(const Mat &B) {
    int n = height(), m = B.width(), p = width();
    assert(p == B.height());
    vector<vector<T>> C(n, vector<T>(m, 0));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        for (int k = 0; k < p; k++) {
          C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]) % mod;
        }
      }
    }
    A.swap(C);
    return (*this);
  }
  Mat &operator^=(long long int k) {
    Mat B = Mat::I(height());
    while (k) {
      if (k % 2) B *= (*this);
      (*this) *= (*this);
      k >>= 1LL;
    }
    A.swap(B.A);
    return (*this);
  }
  Mat operator+(const Mat &B) const { return (Mat(*this) += B); }
  Mat operator-(const Mat &B) const { return (Mat(*this) -= B); }
  Mat operator*(const Mat &B) const { return (Mat(*this) *= B); }
  Mat operator^(const Mat &B) const { return (Mat(*this) ^= B); }
};
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long long int n, k;
  cin >> n >> k;
  Mat<long long int> A(2 * k + 3, 2 * k + 3), B(2 * k + 3, 1);
  long long int sum = (1 + (1LL << (k + 1))) % mod;
  if (n == 1) {
    printf("1\n");
  } else if (n == 2) {
    printf("%lld\n", sum);
  } else {
    for (int i = 0; i <= k; i++) {
      B[i][0] = (1LL << (k - i + 1)) % mod;
    }
    for (int i = k + 1; i <= 2 * k + 1; i++) {
      B[i][0] = 1;
    }
    B[2 * k + 2][0] = sum;
    for (int i = 0; i <= k; i++) {
      A[k + 1 + i][i] = 1;
    }
    for (int i = 0; i <= k; i++) {
      int t = k - i;
      for (int j = 0; j <= t; j++) {
        A[i][k - j] = p.comb(t, j);
        A[i][2 * k + 1 - j] = (1LL << (t - j)) % mod * p.comb(t, j) % mod;
      }
    }
    for (int i = 0; i < 2 * k + 3; i++) {
      A[2 * k + 2][i] = A[0][i];
    }
    A[2 * k + 2][2 * k + 2] = 1;
    A ^= (n - 2);
    B = A * B;
    printf("%lld\n", B[2 * k + 2][0]);
  }
}