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 mod = 1000000007;
const int K = 85;
long long ncr[K][K];
inline void pre() {
  memset(ncr, 0, sizeof(ncr));
  ncr[0][0] = 1;
  for (int n = 1; n < K; n++) {
    ncr[n][0] = 1;
    for (int r = 1; r <= n; r++) {
      ncr[n][r] = (ncr[n - 1][r] + ncr[n - 1][r - 1]) % mod;
    }
  }
}
inline void product(long long A[K][K], long long B[K][K], long long C[K][K],
                    int sz) {
  for (int i = 0; i < sz; i++) {
    for (int j = 0; j < sz; j++) {
      C[i][j] = 0;
      for (int k = 0; k < sz; k++) {
        C[i][j] += A[i][k] * B[k][j] % mod;
        if (C[i][j] >= mod) C[i][j] -= mod;
      }
    }
  }
}
inline void power(long long A[K][K], long long n, long long B[K][K], int sz) {
  long long C[K][K];
  for (int i = 0; i < sz; i++) {
    for (int j = 0; j < sz; j++) {
      B[i][j] = (i == j);
    }
  }
  while (n) {
    if (n & 1) {
      product(B, A, C, sz);
      for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
          B[i][j] = C[i][j];
        }
      }
    }
    product(A, A, C, sz);
    for (int i = 0; i < sz; i++) {
      for (int j = 0; j < sz; j++) {
        A[i][j] = C[i][j];
      }
    }
    n >>= 1;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << setprecision(32);
  pre();
  long long A[K][K];
  long long n;
  int k;
  cin >> n >> k;
  memset(A, 0, sizeof(A));
  if (n == 1) {
    cout << 1 << endl;
    exit(0);
  }
  if (n == 2) {
    long long ret = (1LL << (k + 1)) + 1;
    ret %= mod;
    cout << ret << endl;
    exit(0);
  }
  int sz = 2 * k + 3;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= i; j++) {
      A[i][j] = ncr[i][j];
      A[i][j + k + 1] = ncr[i][j] * ((1LL << (i - j)) % mod) % mod;
    }
    A[i + k + 1][i] = 1;
    A[i][2 * k + 2] = (1 + (1LL << i)) % mod;
  }
  A[2 * k + 2][2 * k + 2] = 1;
  long long B[K][K];
  power(A, n - 1, B, sz);
  long long ans = 0;
  for (int i = 0; i <= k; i++) {
    ans += B[k][i];
  }
  ans += B[k][2 * k + 2];
  ans %= mod;
  cout << ans << endl;
  return 0;
}