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 int LIM = 83;
int k;
long long comb[50][50], pt[50], c[LIM][LIM];
long long n;
void operator*(vector<vector<long long> > &a, vector<vector<long long> > &b) {
  for (int i = 0; i < LIM; i++)
    for (int j = 0; j < LIM; j++) c[i][j] = 0;
  for (int l = 0; l < LIM; l++)
    for (int i = 0; i < LIM; i++)
      for (int j = 0; j < LIM; j++)
        c[i][j] = (((c[i][j]) + (((a[i][l]) * (b[l][j])))) % 1000000007);
  for (int i = 0; i < LIM; i++)
    for (int j = 0; j < LIM; j++) a[i][j] = c[i][j];
}
int com(int a, int b) {
  if (b < 0) return 0;
  return comb[a][b];
}
int main() {
  cin >> n >> k;
  n--;
  pt[0] = 1;
  for (int j = 0; j <= k; j++) {
    comb[j][0] = 1;
    comb[j][j] = 1;
    if (j) pt[j] = ((pt[j - 1]) * (2)) % 1000000007;
  }
  for (int i = 1; i <= k; i++)
    for (int j = 1; j < i; j++)
      comb[i][j] = (((comb[i - 1][j - 1]) + (comb[i - 1][j])) % 1000000007);
  vector<vector<long long> > mat(LIM, vector<long long>(LIM, 0)),
      cur(LIM, vector<long long>(LIM, 0));
  for (int i = 0; i < LIM; i++) cur[i][i] = 1;
  for (int i = 0; i <= 2 * k + 1; i++)
    for (int j = 0; j <= 2 * k + 1; j++)
      if (i >= k + 1 || j >= k + 1)
        mat[i][j] = com(j % (k + 1), (j % (k + 1)) - (i % (k + 1)));
  mat[2 * k + 2][2 * k + 2] = mat[2 * k + 1][2 * k + 2] = 1;
  for (int i = 0; i < 60; i++, mat * mat)
    if ((1ll << i) & n) cur *mat;
  int answer = 0;
  for (int i = 0; i <= k; i++)
    answer = (((answer) + (((pt[i]) * (cur[i][2 * k + 2])))) % 1000000007);
  for (int i = k + 1; i <= 2 * k + 1; i++)
    answer = (((answer) + (((((pt[i - k - 1]) * (2))) * (cur[i][2 * k + 2])))) %
              1000000007);
  answer = (((answer) + (cur[2 * k + 2][2 * k + 2])) % 1000000007);
  cout << answer << endl;
}