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>
#pragma GCC optimise("ofast")
#pragma GCC optimise("unroll-loops")
using namespace std;
const int N = 100;
const long long MOD = 1000000000 + 7;
const long long INF = 1000000000000000000;
const long long LOG = 25;
struct Matrix {
  long long n, m, M[N][N];
  Matrix(int n1, int m1) {
    n = n1;
    m = m1;
    Clear();
  }
  void Clear() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        M[i][j] = 0;
      }
    }
  }
  void Identity() {
    Clear();
    if (n != m) {
      cerr << "Cannot Make Identity Matrix Not Compatible\n";
      return;
    }
    for (int i = 0; i < n; i++) {
      M[i][i] = 1;
    }
  }
  void Print() {
    cerr << "***\n";
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cerr << M[i][j] << ' ';
      }
      cerr << '\n';
    }
    cerr << "***\n";
  }
  void Fill(int t) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        M[i][j] = t;
      }
    }
  }
  Matrix operator*(const Matrix &T) {
    Matrix R = Matrix(n, T.m);
    R.Clear();
    if (m != T.n) {
      cerr << "Matrices not Compatible for multiplying\n";
      return R;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < T.m; j++) {
        for (int k = 0; k < m; k++) {
          R.M[i][j] = (R.M[i][j] + M[i][k] * 1ll * T.M[k][j]) % MOD;
        }
      }
    }
    return R;
  }
  Matrix operator+(const Matrix &T) {
    Matrix R = Matrix(n, m);
    R.Clear();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        R.M[i][j] = (M[i][j] + T.M[i][j]) % MOD;
      }
    }
    return R;
  }
  Matrix operator^(const long long t) {
    Matrix res = Matrix(n, m);
    res.Identity();
    if (t == 0) return res;
    Matrix T = Matrix(n, m);
    T.Clear();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        T.M[i][j] = M[i][j];
      }
    }
    long long p = t;
    while (p) {
      if (p & 1) {
        res = res * T;
      }
      p >>= 1;
      T = T * T;
    }
    return res;
  }
};
long long n, k;
long long POW(long long x, long long t) {
  long long res = 1;
  while (t) {
    if (t & 1) res *= x, res %= MOD;
    t >>= 1;
    x *= x;
    x %= MOD;
  }
  return res;
}
long long dp[N][N];
void calc() {
  dp[0][0] = 1;
  for (int i = 1; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (j > i) continue;
      if (j == 0)
        dp[i][j] = 1;
      else
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
    }
  }
  return;
}
int main() {
  cin >> n >> k;
  calc();
  Matrix M(2 * k + 3, 2 * k + 3);
  Matrix A(1, 2 * k + 3);
  for (int i = 0; i < 2 * k + 3; i++) {
    if (i < k + 1) {
      A.M[0][i] = 2 * POW(2, i) % MOD;
    } else if (i != 2 * k + 2) {
      A.M[0][i] = POW(2, i - k - 1);
    } else {
      A.M[0][i] = 1;
    }
  }
  for (int i = 0; i < 2 * k + 3; i++) {
    if (i < k + 1) {
      for (int j = 0; j < k + 1; j++) M.M[j][i] = dp[i][j];
      for (int j = k + 1; j < 2 * k + 2; j++) M.M[j][i] = dp[i][j - k - 1];
    } else if (i < 2 * k + 2) {
      for (int j = 0; j < k + 1; j++) M.M[j][i] = dp[i - k - 1][j];
    } else {
      M.M[k][2 * k + 2] = 1;
      M.M[2 * k + 2][2 * k + 2] = 1;
    }
  }
  M = M ^ (n - 1);
  A = A * M;
  cout << A.M[0][2 * k + 2];
  return 0;
}