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;
long long n;
struct cv {
  int x, y;
  long long a[100][100];
  friend cv operator*(cv p, cv q) {
    cv tm;
    tm.x = p.x;
    tm.y = q.y;
    for (int i = 0; i < q.y; i++) {
      for (int j = 0; j < p.x; j++) {
        tm.a[j][i] = 0;
        for (int k = 0; k < p.y; k++) {
          tm.a[j][i] += p.a[j][k] * q.a[k][i] % 1000000007;
          tm.a[j][i] %= 1000000007;
        }
      }
    }
    return tm;
  }
  void pr() {
    printf("%d %d\n", x, y);
    for (int i = 0; i < x; i++) {
      for (int j = 0; j < y; j++) printf("%lld ", a[i][j]);
      printf("\n");
    }
  }
};
cv po(cv x, long long y) {
  cv tm;
  tm.x = tm.y = x.x;
  memset(tm.a, 0, sizeof(tm.a));
  for (int i = 0; i < tm.x; i++) tm.a[i][i] = 1;
  while (y) {
    if (y & 1) tm = tm * x;
    x = x * x;
    y /= 2;
  }
  return tm;
}
int d[100][100];
int main() {
  int k;
  cin >> n >> k;
  k++;
  cv bb;
  bb.x = 2 * k + 1, bb.y = 1;
  bb.a[0][0] = 0;
  for (int i = 1; i <= 2 * k; i++) bb.a[i][0] = 1;
  cv dd;
  dd.x = dd.y = 2 * k + 1;
  memset(dd.a, 0, sizeof(dd.a));
  d[1][1] = 1;
  for (int i = 2; i <= k; i++) {
    for (int j = 1; j <= i; j++)
      d[i][j] = (d[i - 1][j - 1] + d[i - 1][j]) % 1000000007;
  }
  dd.a[0][0] = dd.a[0][1] = 1;
  for (int i = 1; i <= k; i++) {
    for (int j = i; j <= k; j++) {
      dd.a[2 * i - 1][j * 2 - 1] = dd.a[2 * i - 1][j * 2] =
          dd.a[2 * i][j * 2 - 1] = d[k + 1 - i][j - i + 1];
    }
  }
  dd = po(dd, n);
  bb = dd * bb;
  printf("%lld", bb.a[0][0]);
  return 0;
}