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 N = 100005;
const int mo = 1000000007;
const int inf = (int)1e9;
inline int IN() {
  char ch;
  (ch = getchar());
  int f = 0, x = 0;
  for (; ((ch) == '\n' || (ch) == '\r' || (ch) == '\t' || (ch) == ' ');
       (ch = getchar()))
    ;
  if (ch == '-') f = 1, (ch = getchar());
  for (; !((ch) == '\n' || (ch) == '\r' || (ch) == '\t' || (ch) == ' ');
       (ch = getchar()))
    x = x * 10 + ch - '0';
  return (f) ? (-x) : (x);
}
int Pow(int x, int y, int p) {
  int A = 1;
  for (; y; y >>= 1, x = (long long)x * x % p)
    if (y & 1) A = (long long)A * x % p;
  return A;
}
long long n;
int k, mat[105][105], E[105][105], tmp[105][105];
int main() {
  cin >> n >> k;
  ++k;
  for (int j = (int)0; j < (int)k; j++) {
    for (int i = (int)0; i <= (int)j; i++) {
      if (i && j)
        mat[i][j] = (mat[i][j - 1] + mat[i - 1][j - 1]) % mo;
      else
        mat[i][j] = 1;
    }
    for (int i = (int)k; i < (int)k * 2; i++) {
      mat[i][j] = mat[i - k][j];
    }
  }
  for (int j = (int)k; j < (int)2 * k; j++) {
    for (int i = (int)0; i < (int)k; i++) mat[i][j] = mat[i][j - k];
  }
  mat[2 * k][2 * k] = 1;
  for (int i = (int)0; i < (int)2 * k; i++) mat[i][2 * k] = mat[i][k - 1];
  k *= 2;
  k++;
  for (int i = (int)0; i < (int)k; i++) E[i][i] = 1;
  for (; n; n >>= 1) {
    if (n & 1) {
      for (int i = (int)0; i < (int)k; i++)
        for (int j = (int)0; j < (int)k; j++) tmp[i][j] = 0;
      for (int u = (int)0; u < (int)k; u++)
        for (int i = (int)0; i < (int)k; i++)
          for (int j = (int)0; j < (int)k; j++) {
            tmp[i][j] = (tmp[i][j] + (long long)E[i][u] * mat[u][j]) % mo;
          }
      for (int i = (int)0; i < (int)k; i++)
        for (int j = (int)0; j < (int)k; j++) E[i][j] = tmp[i][j];
    }
    for (int i = (int)0; i < (int)k; i++)
      for (int j = (int)0; j < (int)k; j++) tmp[i][j] = 0;
    for (int u = (int)0; u < (int)k; u++)
      for (int i = (int)0; i < (int)k; i++)
        for (int j = (int)0; j < (int)k; j++) {
          tmp[i][j] = (tmp[i][j] + (long long)mat[i][u] * mat[u][j]) % mo;
        }
    for (int i = (int)0; i < (int)k; i++)
      for (int j = (int)0; j < (int)k; j++) mat[i][j] = tmp[i][j];
  }
  printf("%d\n", E[0][k - 1]);
  return 0;
}