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;
template <class T>
inline bool chkmin(T& x, T y) {
  return x > y ? x = y, true : false;
}
template <class T>
inline bool chkmax(T& x, T y) {
  return x < y ? x = y, true : false;
}
inline long long read(void) {
  long long x, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x * f;
}
struct Matrix {
  enum { maxn = 83 };
  long long data[maxn + 1][maxn + 1];
  Matrix& clear() {
    memset(data, 0, sizeof(data));
    return *this;
  }
  Matrix& unit() {
    clear();
    for (int i = 1; i <= maxn; ++i) data[i][i] = 1;
    return *this;
  }
  Matrix operator*(const Matrix& o) {
    Matrix ret;
    ret.clear();
    for (int i = 1; i <= maxn; ++i)
      for (int j = 1; j <= maxn; ++j) {
        ret.data[i][j] = 0;
        for (int z = 1; z <= maxn; ++z) {
          ret.data[i][j] += data[i][z] * o.data[z][j] % 1000000007;
          if (ret.data[i][j] >= 1000000007) ret.data[i][j] -= 1000000007;
          ;
        }
      }
    return ret;
  }
  Matrix operator+(const Matrix& o) {
    Matrix ret;
    for (int i = 1; i <= maxn; ++i)
      for (int j = 1; j <= maxn; ++j) {
        ret.data[i][j] = data[i][j] + o.data[i][j];
        if (ret.data[i][j] >= 1000000007) ret.data[i][j] -= 1000000007;
        ;
      }
    return ret;
  }
  Matrix operator^(long long x) {
    Matrix ret = *this;
    if (--x == 0) return ret;
    Matrix cnt = *this;
    while (x) {
      if (x & 1) ret = ret * cnt;
      cnt = cnt * cnt;
      x >>= 1;
    }
    return ret;
  }
} M;
long long n, k;
long long ans, P[50], C[50][50];
void pre() {
  P[0] = 1;
  for (int i = 1; i <= k + 1; ++i) {
    P[i] = P[i - 1] + P[i - 1];
    if (P[i] >= 1000000007) P[i] -= 1000000007;
    ;
  }
  C[0][0] = 1;
  C[1][0] = 1;
  C[1][1] = 1;
  for (int i = 2; i <= k; ++i) {
    C[i][0] = 1;
    C[i][i] = 1;
    for (int j = 1; j <= i - 1; ++j) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
      if (C[i][j] >= 1000000007) C[i][j] -= 1000000007;
      ;
    }
  }
}
int main(void) {
  n = read();
  k = read();
  pre();
  if (n == 1) {
    puts("1");
    return 0;
  }
  for (int i = 1; i <= k + 1; ++i) M.data[i + k + 1][i] = 1;
  for (int i = k + 2; i <= 2 * (k + 1); ++i) {
    for (int j = 1; j <= i - k - 1; ++j)
      M.data[j][i] = P[i - k - 1 - j] * C[i - (k + 2)][j - 1] % 1000000007;
    for (int j = 1; j <= i - k - 1; ++j)
      M.data[j + k + 1][i] = C[i - (k + 2)][j - 1];
  }
  M.data[2 * (k + 1) + 1][2 * (k + 1) + 1] = 1;
  M.data[2 * (k + 1)][2 * (k + 1) + 1] = 1;
  M = M ^ (n - 1);
  ans = M.data[2 * (k + 1) + 1][1];
  for (int i = 1; i <= k + 1; ++i) {
    ans += M.data[i][2 * (k + 1) + 1];
    if (ans >= 1000000007) ans -= 1000000007;
    ;
  }
  for (int i = 1; i <= k + 1; ++i) {
    ans += M.data[i + k + 1][2 * (k + 1) + 1] * P[i] % 1000000007;
    if (ans >= 1000000007) ans -= 1000000007;
    ;
  }
  printf("%lld\n",
         (ans + M.data[2 * (k + 1) + 1][2 * (k + 1) + 1]) % 1000000007);
  return 0;
}