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 MAXN = 101;
const int mod = 1e9 + 7;
int K, dn[MAXN][MAXN], m[MAXN][MAXN], us[MAXN];
int init[MAXN][MAXN], tmp[MAXN][MAXN], res[MAXN][MAXN];
long long N;
inline int add(int a, int b) {
  if (a + b >= mod) return a + b - mod;
  return a + b;
}
inline int mul(int a, int b) { return (long long)a * b % mod; }
int komb(int a, int b) {
  if (dn[a][b] != -1) return dn[a][b];
  if (a < b) return 0;
  if (a == b || !b) return 1;
  if (a == b + 1 || b == 1) return a;
  return dn[a][b] = add(komb(a - 1, b - 1), komb(a - 1, b));
}
void f(int a[MAXN][MAXN], int b[MAXN][MAXN]) {
  for (int i = 1; i <= K + K + 3; i++)
    for (int j = 1; j <= K + K + 3; j++) {
      int sum = 0;
      for (int k = 1; k <= K + K + 3; k++)
        sum = add(sum, mul(a[i][k], b[k][j]));
      tmp[i][j] = sum;
    }
  for (int i = 1; i <= K + K + 3; i++)
    for (int j = 1; j <= K + K + 3; j++) a[i][j] = tmp[i][j];
}
int main() {
  cin >> N >> K;
  if (N == 1) {
    printf("1\n");
    return 0;
  }
  memset(dn, -1, sizeof dn);
  us[0] = 1;
  for (int i = 1; i <= K; i++) us[i] = add(us[i - 1], us[i - 1]);
  m[1][1] = m[2][1] = 1;
  for (int j = 1, i = 3; j <= K + 1; j++, i += 2) m[i - 1][i] = 1;
  for (int j = 1, i = 2; j <= K + 1; j++, i += 2) {
    for (int k = i, asd = 0; k <= K + K + 3; k += 2, asd++) {
      m[k][i] = komb(K - j + 1, asd);
      m[k + 1][i] = mul(komb(K - j + 1, asd), us[asd]);
    }
  }
  for (int i = 1; i <= K + K + 3; i++)
    for (int j = 1; j <= K + K + 3; j++) res[i][j] = m[i][j];
  init[1][1] = 1;
  for (int i = 2, k = K; i <= K + K + 3; i += 2, k--) {
    init[1][i] = mul(2, us[k]);
    init[1][i + 1] = 1;
  }
  N -= 2;
  for (int i = 0; i <= 60; i++) {
    if ((1ll << i) & N) f(res, m);
    f(m, m);
  }
  f(init, res);
  printf("%d\n", init[1][1]);
  return 0;
}