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 read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long K, n, N;
long long C[50][50], bin[50];
struct Jz {
  long long a[95][95];
  Jz() { memset(a, 0, sizeof(a)); }
} A, B;
Jz operator*(Jz A, Jz B) {
  Jz C;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      for (int k = 1; k <= N; k++) {
        C.a[i][j] += A.a[i][k] * B.a[k][j];
        C.a[i][j] %= 1000000007;
      }
  return C;
}
Jz Qsm(Jz B, long long x) {
  long long c = x;
  Jz O = B;
  Jz res;
  for (int i = 1; i <= N; i++) res.a[i][i] = 1;
  while (c) {
    if (c & 1) res = res * O;
    O = O * O;
    c >>= 1;
  }
  return res;
}
void Build_A() {
  N = 2 * (K + 1) + 1;
  for (int i = 1; i <= K + 1; i++)
    A.a[1][i] = (2 * bin[K - i + 1]) % 1000000007;
  for (int i = 1; i <= K + 1; i++) A.a[1][i + K + 1] = 1;
  A.a[1][N] = 0;
}
void Build_B() {
  N = 2 * (K + 1) + 1;
  for (int i = 1; i <= K + 1; i++) {
    int k = K - i + 1;
    for (int j = 0; j <= k; j++) {
      B.a[K + 1 - j][i] = C[k][j];
      B.a[K + 1 + K + 1 - j][i] = (C[k][j] * bin[k - j]) % 1000000007;
    }
  }
  for (int i = 1; i <= K + 1; i++) B.a[i][K + 1 + i] = 1;
  B.a[1][N] = 1;
  B.a[N][N] = 1;
}
int main() {
  n = read();
  K = read();
  bin[0] = 1;
  memset(C, 0, sizeof(C));
  for (int i = 1; i <= 42; i++) bin[i] = (bin[i - 1] << 1);
  if (n == 1) {
    puts("1");
    return 0;
  }
  if (n == 2) {
    long long ans = bin[K];
    cout << (ans + 1) % 1000000007 << endl;
  } else {
    memset(C, 0, sizeof(C));
    for (int i = 0; i <= K; i++) C[i][0] = 1;
    for (int i = 1; i <= K; i++) {
      C[i][i] = 1;
      for (int j = 1; j <= i - 1; j++)
        C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
    }
    Build_A();
    Build_B();
    B = Qsm(B, n - 1);
    Jz Ans = A * B;
    cout << (Ans.a[1][N] + 1) % 1000000007 << endl;
  }
  return 0;
}