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 M = 1000000007;
void printMat(vector<vector<long long> >& a) {
  for (auto i : a) {
    for (auto j : i) {
      cout << j;
    }
    cout << endl;
  }
}
vector<vector<long long> > operator*(const vector<vector<long long> >& a,
                                     const vector<vector<long long> >& b) {
  int rows = a.size();
  int n = a[0].size();
  int cols = b[0].size();
  vector<vector<long long> > c(rows, vector<long long>(cols, 0));
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      for (int k = 0; k < n; k++) {
        c[i][j] = (c[i][j] + (a[i][k] * b[k][j])) % M;
      }
    }
  }
  return c;
}
vector<vector<long long> > operator^(const vector<vector<long long> >& a,
                                     long long b) {
  if (b == 1) {
    return a;
  } else {
    if (b % 2 == 0) {
      return (a * a) ^ (b / 2);
    } else {
      return a * ((a * a) ^ ((b - 1) / 2));
    }
  }
}
long long power(int a, int b) {
  long long ans = 1;
  for (int i = 0; i < b; i++) {
    ans = ans * a % M;
  }
  return ans;
}
int main() {
  long long n;
  int m;
  cin >> n;
  cin >> m;
  if (n == 1) {
    cout << 1;
  } else {
    int k = m + 1;
    vector<vector<long long> > myMat((2 * k + 1),
                                     vector<long long>(2 * k + 1, 0));
    vector<vector<long long> > answers((2 * k + 1), vector<long long>(1, 0));
    answers[0][0] = 1;
    for (int i = 0; i < k; i++) {
      answers[i + 1][0] = 2 * power(2, k - 1 - i) % M;
      answers[i + k + 1][0] = power(2, k - 1 - i) % M;
    }
    myMat[0][0] = 1;
    myMat[0][1] = 1;
    myMat[k][k] = 1;
    myMat[k][2 * k] = 1;
    myMat[2 * k][k] = 1;
    for (int i = 1; i < k; i++) {
      myMat[k - i][k] = 1;
      myMat[k - i][2 * k] = 1;
      myMat[2 * k - i][k] = 1;
      for (int j = 1; j < k; j++) {
        myMat[k - i][j] = myMat[k - i + 1][j] + myMat[k - i + 1][j + 1];
        myMat[k - i][k + j] =
            myMat[k - i + 1][k + j + 1] + myMat[k - i + 1][k + j];
        myMat[2 * k - i][j] =
            myMat[2 * k - i + 1][j] + myMat[2 * k - i + 1][j + 1];
      }
    }
    long long nr = n - 1;
    auto ans = myMat ^ nr;
    cout << (ans * answers)[0][0];
  }
}