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;
inline char gc() {
  static char buf[1000000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <typename T>
inline T frd(T x) {
  int f = 1;
  char ch = gc();
  for (; ch < '0' || ch > '9'; ch = gc())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = gc()) x = (x << 1) + (x << 3) + ch - '0';
  return x * f;
}
template <typename T>
inline T read(T x) {
  int f = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 1) + (x << 3) + ch - '0';
  return x * f;
}
inline void print(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
const int N = 85, P = 1e9 + 7;
struct Matrix {
  int V[N][N];
  Matrix() { memset(V, 0, sizeof(V)); }
  void clear() { memset(V, 0, sizeof(V)); }
  void init() {
    clear();
    for (int i = 0; i < N; i++) V[i][i] = 1;
  }
};
Matrix operator*(Matrix x, Matrix y) {
  Matrix z;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
        z.V[i][k] = (1ll * x.V[i][j] * y.V[j][k] + z.V[i][k]) % P;
  return z;
}
Matrix mlt(Matrix a, long long b) {
  Matrix res;
  res.init();
  for (; b; b >>= 1, a = a * a)
    if (b & 1) res = res * a;
  return res;
}
int fac[N + 10], inv[N + 10];
int C(int n, int m) {
  return n < m ? 0 : 1ll * fac[n] * inv[m] % P * inv[n - m] % P;
}
int main() {
  fac[0] = inv[0] = inv[1] = 1;
  for (int i = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % P;
  for (int i = 2; i <= N; i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
  for (int i = 1; i <= N; i++) inv[i] = 1ll * inv[i - 1] * inv[i] % P;
  Matrix Ans, Trans;
  long long n = read(0ll);
  int k = read(0);
  for (int i = 0; i < (k + 1) << 1; i++) Ans.V[0][i] = 1;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= i; j++) {
      Trans.V[j << 1][i << 1] = C(i, j);
      Trans.V[j << 1 | 1][i << 1] = C(i, j);
      Trans.V[j << 1][i << 1 | 1] = C(i, j);
    }
  }
  Trans.V[k << 1][(k + 1) << 1] = 1;
  Trans.V[(k + 1) << 1][(k + 1) << 1] = 1;
  Ans = Ans * mlt(Trans, n);
  printf("%d\n", Ans.V[0][(k + 1) << 1]);
  putchar('\n');
  return 0;
}