#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
const long long INFL = LLONG_MAX;
const long double pi = acos(-1);
const int MOD = 1e9 + 7;
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline int mul(int a, int b) {
  long long x = a * 1ll * b;
  x %= MOD;
  return (int)x;
}
vector<vector<int> > mul(vector<vector<int> > m1, vector<vector<int> > m2) {
  int p = int(m1.size());
  int q = int(m1[0].size());
  int r = int(m2[0].size());
  vector<vector<int> > ret(p, vector<int>(r));
  for (int(i) = 0, j123 = p; (i) < j123; (i)++)
    for (int(j) = 0, j123 = r; (j) < j123; (j)++)
      for (int(k) = 0, j123 = q; (k) < j123; (k)++)
        ret[i][j] = add(ret[i][j], mul(m1[i][k], m2[k][j]));
  return ret;
}
vector<vector<int> > mypow(vector<vector<int> > m, long long n) {
  int len = int(m.size());
  vector<vector<int> > ret(len, vector<int>(len));
  for (int i = 0; i < len; i++) ret[i][i] = 1;
  while (n) {
    if (n & 1) ret = mul(ret, m);
    n >>= 1;
    m = mul(m, m);
  }
  return ret;
}
void print(vector<vector<int> > m) {
  int p = int(m.size());
  int q = int(m[0].size());
  for (int(i) = 0, j123 = p; (i) < j123; (i)++)
    for (int(j) = 0, j123 = q; (j) < j123; (j)++)
      cout << m[i][j] << (j + 1 < q ? ' ' : '\n');
}
long long N;
int K;
int choose[100][100];
int main() {
  ios_base::sync_with_stdio(0);
  cout.precision(15);
  cout << fixed;
  cout.tie(0);
  cin.tie(0);
  cin >> N >> K;
  choose[0][0] = 1;
  for (int i = 1; i <= 88; i++) {
    choose[i][0] = choose[i][i] = 1;
    for (int j = 1; j < i; j++)
      choose[i][j] = add(choose[i - 1][j - 1], choose[i - 1][j]);
  }
  int len = (K + 1) * 2 + 1;
  vector<vector<int> > m(len, vector<int>(len));
  for (int kk = 0; kk <= K; kk++) {
    for (int j = 0; j <= kk; j++) {
      m[kk][j] = choose[kk][j];
    }
  }
  for (int kk = 0; kk <= K; kk++) {
    for (int j = 0; j <= kk; j++) {
      for (int l = 0; l <= j; l++) {
        int x = mul(choose[kk][j], choose[j][l]);
        m[kk][K + 1 + l] = add(m[kk][K + 1 + l], x);
      }
    }
  }
  for (int delta = 0; delta <= K; delta++) {
    m[K + 1 + delta][delta] = 1;
  }
  m[len - 1][K] = 1;
  m[len - 1][len - 1] = 1;
  vector<vector<int> > m2(len, vector<int>(1));
  for (int i = 0; i < len; i++) {
    if (i <= K) {
      int val = 1;
      for (int(jjjjj) = 0, j123 = i + 1; (jjjjj) < j123; (jjjjj)++)
        val = mul(val, 2);
      m2[i][0] = val;
    } else {
      m2[i][0] = 1;
    }
  }
  vector<vector<int> > ret = mypow(m, N - 1);
  vector<vector<int> > ret2 = mul(ret, m2);
  long long ans = ret2[len - 1][0];
  ans %= MOD;
  ans += MOD;
  ans %= MOD;
  cout << ans << '\n';
}
