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;
const int Mod = 1e9 + 7;
struct Matrix {
  long long m[85][85];
  Matrix(int x) {
    for (int i = 0; i < 85; i++)
      for (int j = 0; j < 85; j++)
        if (i == j)
          m[i][j] = x;
        else
          m[i][j] = 0;
  }
};
long long n, c[50][50];
int k;
void init() {
  c[0][0] = 1;
  c[1][0] = c[1][1] = 1;
  for (int i = 2; i <= 45; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;
  }
}
Matrix multi(Matrix A, Matrix B) {
  Matrix ans(0);
  int size = 2 * k + 3;
  for (int p = 1; p <= size; p++)
    for (int i = 1; i <= size; i++)
      for (int j = 1; j <= size; j++)
        ans.m[i][j] = (ans.m[i][j] + A.m[i][p] * B.m[p][j]) % Mod;
  return ans;
}
Matrix quick_pow(Matrix A, long long b) {
  Matrix ans(1);
  while (b) {
    if (b & 1) ans = multi(ans, A);
    A = multi(A, A);
    b >>= 1;
  }
  return ans;
}
long long Pow(long long a, int b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % Mod;
    a = (a * a) % Mod;
    b >>= 1;
  }
  return ans;
}
int main() {
  cin >> n >> k;
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  Matrix A(0);
  init();
  A.m[1][1] = 1;
  for (int i = 2; i <= k + 2; i++) A.m[i][1] = c[k][k - i + 2];
  for (int i = k + 3; i <= 2 * k + 3; i++) A.m[i][1] = c[k][2 * k + 3 - i];
  for (int j = 2; j <= k + 2; j++) {
    int i = j, p = k - j + 2, q = k - j + 2;
    while (i <= k + 2) {
      A.m[i][j] = c[p][q];
      i++;
      q--;
    }
    i = j + k + 1;
    q = k - j + 2;
    while (i <= 2 * k + 3) {
      A.m[i][j] = c[p][q];
      i++;
      q--;
    }
  }
  for (int j = k + 3; j <= 2 * k + 3; j++) {
    int i = j - k - 1, p = 2 * k + 3 - j, q = 2 * k + 3 - j;
    while (i <= k + 2) {
      A.m[i][j] = c[p][q];
      i++;
      q--;
    }
  }
  A = quick_pow(A, n - 2);
  long long ans = (1 + Pow(2, k + 1)) * A.m[1][1] % Mod;
  for (int i = 2; i <= k + 2; i++) {
    ans = (ans + Pow(2, k - i + 3) * A.m[i][1]) % Mod;
  }
  for (int i = k + 3; i <= 2 * k + 3; i++) {
    ans = (ans + Pow(2, 2 * k + 3 - i) * A.m[i][1]) % Mod;
  }
  cout << ans << endl;
  return 0;
}