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;
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
                                           __c, qu[55];
int __f, qr, _eof;
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc(char &x) {
  x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                   (iS == iT ? EOF : *iS++))
                : *iS++);
}
inline void pc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
inline void pstr(const char *s) {
  int __len = strlen(s);
  for (__f = 0; __f < __len; ++__f) pc(s[__f]);
}
inline void gstr(char *s) {
  for (__c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++);
       __c < 32 || __c > 126 || __c == ' ';)
    __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                    : *iS++);
  for (; __c > 31 && __c < 127 && __c != ' ';
       ++s, __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++))
    *s = __c;
  *s = 0;
}
template <class I>
inline bool gi(I &x) {
  _eof = 0;
  for (__f = 1,
      __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                        (iS == iT ? EOF : *iS++))
                      : *iS++);
       (__c < '0' || __c > '9') && !_eof;
       __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++)) {
    if (__c == '-') __f = -1;
    _eof |= __c == EOF;
  }
  for (x = 0; __c <= '9' && __c >= '0' && !_eof;
       __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++))
    x = x * 10 + (__c & 15), _eof |= __c == EOF;
  x *= __f;
  return !_eof;
}
template <class I>
inline void print(I x) {
  if (!x) pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) pc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::gc;
using io::gi;
using io::gstr;
using io::pc;
using io::print;
using io::pstr;
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1000000007;
template <typename T, int S>
struct mat {
  T dat[S][S];
  void init() {
    for (int i = (0); i < (S); i++)
      for (int j = (0); j < (S); j++) dat[i][j] = 0;
  }
  T *operator[](int a) { return dat[a]; }
  T const *operator[](int a) const { return dat[a]; }
  mat mult(const mat &b) const {
    mat ans;
    ans.init();
    for (int i = (0); i < (S); i++)
      for (int j = (0); j < (S); j++)
        for (int k = (0); k < (S); k++)
          ans[i][k] = (ans[i][k] + dat[i][j] * b[j][k]) % MOD;
    return ans;
  }
};
using matt = mat<ll, 83>;
matt qpow(const matt &b, const ll &e) {
  if (e == 1) return b;
  if (!(e & 1)) return qpow(b.mult(b), e >> 1);
  return qpow(b, e - 1).mult(b);
}
int p2[42];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  int k;
  gi(n), gi(k);
  if (n == 1) {
    pc('1');
    return 0;
  }
  matt v;
  v.init();
  p2[0] = 1;
  for (int i = (1); i < ((k + 1) + 1); i++) p2[i] = (p2[i - 1] << 1) % MOD;
  v[0][0] = 1;
  for (int i = (0); i < (k + 1); i++) v[i + 1][k + i + 2] = 1;
  for (int i = (0); i < (k + 1); i++)
    for (int j = (0); j < (i + 1); j++) {
      if (!(i | j))
        v[k + 2][k + 2] = 1;
      else
        v[k + i + 2][k + j + 2] =
            (v[k + i + 1][k + j + 1] + v[k + i + 1][k + j + 2]) % MOD;
      v[k + i + 2][j + 1] = 1ll * v[k + i + 2][k + j + 2] * p2[i - j] % MOD;
    }
  for (int i = (1); i < ((2 * k + 2) + 1); i++) v[0][i] = v[2 * k + 2][i];
  matt i;
  i.init();
  i[0][0] = i[1][0] = 1;
  for (int r = (0); r < (k + 1); r++) i[k + r + 2][0] = 1;
  print(qpow(v, n - 1).mult(i)[0][0]);
}