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;
void _fill_int(int* p, int val, int rep) {
  int i;
  for (i = 0; i < rep; i++) p[i] = val;
}
signed long long GETi() {
  signed long long i;
  scanf("%lld", &i);
  return i;
}
signed long long N, K;
signed long long mo = 1000000007;
const int CN = 1001;
signed long long C[CN][CN];
const int MAT = 85;
signed long long G[MAT][MAT], G2[MAT][MAT];
void powmat(signed long long p, int n, signed long long a[MAT][MAT],
            signed long long r[MAT][MAT]) {
  int i, x, y, z;
  signed long long a2[MAT][MAT];
  for (x = 0; x < n; x++)
    for (y = 0; y < n; y++) a2[x][y] = a[x][y];
  for (x = 0; x < n; x++)
    for (y = 0; y < n; y++) r[x][y] = 0;
  for (i = 0; i < n; i++) r[i][i] = 1;
  while (p) {
    signed long long h[MAT][MAT];
    if (p % 2) {
      for (x = 0; x < n; x++)
        for (y = 0; y < n; y++) {
          h[x][y] = 0;
          for (z = 0; z < n; z++) h[x][y] += (r[x][z] * a2[z][y]) % mo;
          h[x][y] %= mo;
        }
      for (x = 0; x < n; x++)
        for (y = 0; y < n; y++) r[x][y] = h[x][y];
    }
    for (x = 0; x < n; x++)
      for (y = 0; y < n; y++) {
        h[x][y] = 0;
        for (z = 0; z < n; z++) h[x][y] += (a2[x][z] * a2[z][y]) % mo;
        h[x][y] %= mo;
      }
    for (x = 0; x < n; x++)
      for (y = 0; y < n; y++) a2[x][y] = h[x][y];
    p >>= 1;
  }
}
void solve() {
  int f, i, j, k, l, x, y;
  cin >> N >> K;
  if (N == 1) return (void)printf("1\n");
  for (x = 0; x < CN; x++) C[x][0] = C[x][x] = 1;
  for (i = 1; i < CN; i++)
    for (j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mo;
  for (i = 0; i < K + 1; i++) {
    for (j = 0; j < i + 1; j++) {
      G[i][j] = C[i][j];
      for (l = 0; l < j + 1; l++)
        G[i][l + 41] += C[i][j] * C[j][l], G[i][l + 41] %= mo;
    }
  }
  memmove(G[82], G[K], sizeof(G[K]));
  for (i = 41; i < 82; i++) G[i][i - 41] = 1;
  G[82][82] = 1;
  G[83][82] = 1;
  powmat(N - 1, 84, G, G2);
  signed long long ret = 0;
  for (i = 0; i < 41; i++) ret += G2[82][i];
  ret += G2[82][82] + G2[82][41];
  cout << ret % mo << endl;
}
int main(int argc, char** argv) {
  string s;
  if (argc == 1) ios::sync_with_stdio(false);
  for (int i = 1; i < argc; i++) s += argv[i], s += '\n';
  for (int i = s.size() - 1; i >= 0; i--) ungetc(s[i], stdin);
  solve();
  return 0;
}