#include <bits/stdc++.h>
const int maxk = 50, maxm = maxk << 1;
const long long p = 1000000007;
long long n, k, m, C[maxk][maxk];
struct _matrix {
  long long num[maxm][maxm];
} E, trans;
inline _matrix matmul(_matrix A, _matrix B) {
  _matrix ans;
  for (int i = 0; i <= m; i++)
    for (int j = 0; j <= m; j++) {
      ans.num[i][j] = 0;
      for (int o = 0; o <= m; o++)
        ans.num[i][j] = (ans.num[i][j] + A.num[i][o] * B.num[o][j] % p) % p;
    }
  return ans;
}
_matrix qpow(_matrix A, long long r) {
  _matrix ans = E;
  for (_matrix t = A; r; r >>= 1, t = matmul(t, t))
    if (r & 1) ans = matmul(ans, t);
  return ans;
}
int main() {
  scanf("%I64d%I64d", &n, &k);
  m = ((k + 1) << 1) + 1 - 1;
  for (int i = 0; i <= k; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
  }
  for (int i = 0; i <= m; i++) E.num[i][i] = 1;
  trans.num[0][0] = trans.num[1][0] = 1;
  for (int i = 1; i <= k + 1; i++)
    for (int j = i; j <= k + 1; j++)
      trans.num[j][i] = trans.num[j + k + 1][i] = trans.num[j][i + k + 1] =
          C[k - i + 1][k - j + 1];
  _matrix res = qpow(trans, n);
  long long ans = 0;
  for (int i = 1; i <= m; i++) ans = (ans + res.num[i][0]) % p;
  printf("%I64d\n", ans);
  return 0;
}
