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 long long MXN = 2e5 + 10;
const long long MXZ = 100 + 10;
const long long Mod = 1e9 + 7;
struct Matrix {
  int n, m;
  long long M[MXZ][MXZ];
  Matrix(int _n, int _m, int num = 0) {
    n = _n, m = _m;
    if (num == -1) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          M[i][j] = (i == j);
        }
      }
    } else {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          M[i][j] = num;
        }
      }
    }
  }
  void Print(bool f = 0) {
    cerr << "=======N.N=======\n";
    if (f) cerr << "Size : " << n << ' ' << m << '\n';
    for (int i = 0; i < n; i++, cerr << '\n') {
      for (int j = 0; j < m; j++) cerr << M[i][j] << ' ';
    }
    cerr << "=======N.N=======\n";
  }
  Matrix operator+(const Matrix &T) {
    Matrix R = Matrix(n, m);
    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 Matrix &T) {
    Matrix R = Matrix(n, T.m);
    if (m != T.n) {
      cerr << "Cannot * Matrices !" << '\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] * T.M[k][j] % Mod)) % Mod;
        }
      }
    }
    return R;
  }
  Matrix operator^(const long long t) {
    Matrix R = Matrix(n, m, -1);
    if (n != m) {
      cerr << "Cannot ^ Matrice with n != m !" << '\n';
      return R;
    }
    if (t == 0) return R;
    Matrix T = Matrix(n, m);
    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 & 1LL) R = R * T;
      T = (T * T), p /= 2;
    }
    return R;
  }
};
long long power(long long a, long long b) {
  return (!b ? 1 : power(a * a % Mod, b / 2) * (b & 1LL ? a : 1) % Mod);
}
long long inv(long long x) { return power(x, Mod - 2); }
long long F[MXZ], I[MXZ];
long long Ch(long long n, long long r) {
  if (r < 0 || r > n) return 0;
  return (F[n] * I[r] % Mod) * I[n - r] % Mod;
}
long long n, k, ans;
long long fib[MXZ];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  F[0] = I[0] = 1, fib[0] = fib[1] = 1;
  for (int i = 1; i < MXZ; i++) F[i] = F[i - 1] * i % Mod;
  for (int i = 1; i < MXZ; i++) I[i] = I[i - 1] * inv(i) % Mod;
  for (int i = 1; i < MXZ; i++) fib[i] = fib[i - 1] + fib[i - 2];
  Matrix C((k + 1) * 2 + 1, (k + 1) * 2 + 1), M1((k + 1) * 2 + 1, 1);
  for (int i = 0; i <= k; i++) M1.M[i][0] = fib[1];
  M1.M[k + 1][0] = 1;
  for (int i = 0; i <= k; i++) {
    long long id = (i + k + 1);
    C.M[id][i] = 1;
  }
  C.M[(k + 1) * 2][(k + 1) * 2] = 1, C.M[(k + 1) * 2][k] = 1;
  for (int kp = 0; kp <= k; kp++) {
    for (int j = 0; j <= k; j++) {
      C.M[kp][j] = Ch(kp, j);
    }
    for (int j = 0; j <= k; j++) {
      long long id = j + k + 1;
      C.M[kp][id] = Ch(kp, j) * power(2, kp - j) % Mod;
    }
  }
  C = (C ^ n);
  M1 = C * M1;
  ans = M1.M[(k + 1) * 2][0];
  cout << ans << '\n';
  return 0;
}