#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
struct Matrix {
  long long m[85][85];
  Matrix(int x) {
    for (int i = 0; i < 85; i++)
      for (int j = 0; j < 85; j++)
        if (i == j)
          m[i][j] = x;
        else
          m[i][j] = 0;
  }
};
long long n, c[50][50];
int k;
void init() {
  c[0][0] = 1;
  c[1][0] = c[1][1] = 1;
  for (int i = 2; i <= 45; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;
  }
}
Matrix multi(Matrix A, Matrix B) {
  Matrix ans(0);
  int size = 2 * k + 3;
  for (int p = 1; p <= size; p++)
    for (int i = 1; i <= size; i++)
      for (int j = 1; j <= size; j++)
        ans.m[i][j] = (ans.m[i][j] + A.m[i][p] * B.m[p][j]) % Mod;
  return ans;
}
Matrix quick_pow(Matrix A, long long b) {
  Matrix ans(1);
  while (b) {
    if (b & 1) ans = multi(ans, A);
    A = multi(A, A);
    b >>= 1;
  }
  return ans;
}
long long Pow(long long a, int b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % Mod;
    a = (a * a) % Mod;
    b >>= 1;
  }
  return ans;
}
int main() {
  cin >> n >> k;
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  Matrix A(0);
  init();
  A.m[1][1] = 1;
  for (int i = 2; i <= k + 2; i++) A.m[i][1] = c[k][k - i + 2];
  for (int i = k + 3; i <= 2 * k + 3; i++) A.m[i][1] = c[k][2 * k + 3 - i];
  for (int j = 2; j <= k + 2; j++) {
    int i = j, p = k - j + 2, q = k - j + 2;
    while (i <= k + 2) {
      A.m[i][j] = c[p][q];
      i++;
      q--;
    }
    i = j + k + 1;
    q = k - j + 2;
    while (i <= 2 * k + 3) {
      A.m[i][j] = c[p][q];
      i++;
      q--;
    }
  }
  for (int j = k + 3; j <= 2 * k + 3; j++) {
    int i = j - k - 1, p = 2 * k + 3 - j, q = 2 * k + 3 - j;
    while (i <= k + 2) {
      A.m[i][j] = c[p][q];
      i++;
      q--;
    }
  }
  A = quick_pow(A, n - 2);
  long long ans = (1 + Pow(2, k + 1)) * A.m[1][1] % Mod;
  for (int i = 2; i <= k + 2; i++) {
    ans = (ans + Pow(2, k - i + 3) * A.m[i][1]) % Mod;
  }
  for (int i = k + 3; i <= 2 * k + 3; i++) {
    ans = (ans + Pow(2, 2 * k + 3 - i) * A.m[i][1]) % Mod;
  }
  cout << ans << endl;
  return 0;
}
