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 <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1, x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1, x2, x3), gn(x4);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  gn(x1, x2, x3, x4), gn(x5);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T1, class T2>
inline void print(T1 x1, T2 x2) {
  printsp(x1), println(x2);
}
template <class T1, class T2, class T3>
inline void print(T1 x1, T2 x2, T3 x3) {
  printsp(x1), printsp(x2), println(x3);
}
template <class T1, class T2, class T3, class T4>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4) {
  printsp(x1), printsp(x2), printsp(x3), println(x4);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4, T5 x5) {
  printsp(x1), printsp(x2), printsp(x3), printsp(x4), println(x5);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int C[110][110];
int a[110][110], tp[110][110], ans[110][110];
int ma;
void multi(int a[110][110], int b[110][110], int c[110][110]) {
  for (int i = 0; i < ma; i++)
    for (int j = 0; j < ma; j++) {
      for (int k = tp[i][j] = 0; k < ma; k++) {
        tp[i][j] = (tp[i][j] + (long long)a[i][k] * b[k][j]) % 1000000007;
      }
    }
  for (int i = 0; i < ma; i++)
    for (int j = 0; j < ma; j++) c[i][j] = tp[i][j];
}
int main() {
  for (int i = 0; i < 50; i++)
    for (int j = 0; j <= i; j++) {
      if (i == 0 || j == 0) {
        C[i][j] = 1;
        continue;
      }
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
    }
  long long n;
  int k;
  gn(n, k);
  ma = 2 * k + 3;
  for (int i = 0; i <= k; i++) {
    int t = 0;
    for (int j = i; j <= k; j++, t++) {
      a[i][j] = C[k - i][t];
    }
  }
  for (int i = 0; i <= k; i++) {
    int t = 0;
    for (int j = i; j <= k; j++, t++) {
      a[i][j + k + 1] =
          (long long)C[k - i][t] * power(2, t, 1000000007) % 1000000007;
    }
  }
  for (int i = 0; i <= k; i++) {
    a[i + k + 1][i] = 1;
  }
  a[2 * k + 2][0] = a[2 * k + 2][2 * k + 2] = 1;
  for (int i = 0; i < ma; i++)
    for (int j = 0; j < ma; j++) ans[i][j] = i == j;
  long long xx = n;
  while (xx) {
    if (xx & 1) multi(ans, a, ans);
    multi(a, a, a);
    xx >>= 1;
  }
  long long num = 0;
  for (int i = 0; i <= k; i++) num = (num + ans[ma - 1][i]) % 1000000007;
  num = (num + ans[ma - 1][ma - 2]) % 1000000007;
  println(num);
  return 0;
}