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;
const long long kMOD = 1e9 + 7;
struct Mat {
  vector<vector<long long>> a;
  int n, m;
  Mat(const vector<vector<long long>> &a) : a(a), n(a.size()), m(a[0].size()) {}
  Mat(int n, int m, int val = 0) : n(n), m(m) {
    a.resize(n);
    for (int i = 0; i < n; ++i) {
      a[i].resize(m);
      if (i < m) a[i][i] = val;
    }
  }
  const vector<long long> &operator[](int i) const { return a[i]; }
  vector<long long> &operator[](int i) { return a[i]; }
  Mat operator*(const Mat &B) const {
    assert(m == B.n);
    Mat ans = Mat(n, B.m);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < B.m; ++j) {
        for (int k = 0; k < m; ++k) {
          ans[i][j] += (a[i][k] * B[k][j]) % kMOD;
        }
        ans[i][j] %= kMOD;
      }
    }
    return ans;
  }
  bool operator==(const Mat &B) const {
    if (!(n == B.n && m == B.m)) return false;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (a[i][j] != B[i][j]) return false;
      }
    }
    return true;
  }
  void print() const {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cout << a[i][j] << " ";
      }
      cout << "\n";
    }
  }
};
Mat b_pow(Mat A, long long deg) {
  if (deg == 0) return Mat(A.n, A.m, 1);
  if (deg == 1) return A;
  if (deg == 2) return A * A;
  return deg % 2 ? b_pow(b_pow(A, deg / 2), 2) * A
                 : b_pow(b_pow(A, deg / 2), 2);
}
int main() {
  srand(time(0));
  long long n, k;
  cin >> n >> k;
  Mat A(2 * k + 3, 2 * k + 3);
  vector<long long> c(k + 1, 0);
  c[0] = 1;
  for (int i = 1; i < k + 1; ++i) {
    long long b = 0;
    for (int j = 0; j <= i; ++j) {
      long long t = b;
      b = c[j] % kMOD;
      c[j] += t;
      c[j] %= kMOD;
    }
  }
  for (int i = 0; i < k + 1; ++i) {
    A[i][i + k + 1] = 1;
    A[i + k + 1][k + 1] = 1;
    A[i + k + 1][0] = (1LL << i) % kMOD;
    for (int j = 1; j <= i; ++j) {
      A[i + k + 1][j + k + 1] = (A[i + k][j + k] + A[i + k][j + k + 1]) % kMOD;
      A[i + k + 1][j] =
          (A[i + k + 1][j + k + 1] * ((1LL << (i - j)) % kMOD)) % kMOD;
    }
    A[2 * k + 2][i] = (c[i] * ((1LL << (k - i)) % kMOD)) % kMOD;
    A[2 * k + 2][i + k + 1] = c[i];
  }
  A[2 * k + 2][2 * k + 2] = 1;
  Mat B(2 * k + 3, 1);
  for (int i = 0; i < 2 * k + 3; ++i) {
    B[i][0] = 1;
  }
  for (int i = 1; i < k + 1; ++i) {
    B[i][0] = 0;
  }
  cout << (b_pow(A, n - 1) * B)[2 * k + 2][0] << "\n";
}