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>
#pragma warning(disable : 4996)
using namespace std;
long long n, m;
map<long long, long long> eq;
map<long long, long long> teq;
long long calcfib(long long x) {
  long long i, j, k, l;
  long long pows[64][2][2] = {0};
  long long u[64] = {
      0,
  };
  pows[0][0][0] = pows[0][0][1] = pows[0][1][0] = 1;
  int now = 0;
  while (x > 0) {
    u[now++] = x % 2;
    x /= 2;
  }
  for (i = 1; i < 63; i++) {
    for (j = 0; j < 2; j++) {
      for (k = 0; k < 2; k++) {
        for (l = 0; l < 2; l++) {
          pows[i][j][k] += pows[i - 1][j][l] * pows[i - 1][l][k];
          pows[i][j][k] %= 1000000007;
        }
      }
    }
  }
  long long rmat[2][2] = {1, 0, 0, 1};
  for (i = 0; i < 63; i++) {
    if (u[i]) {
      long long tmat[2][2] = {
          0,
      };
      for (j = 0; j < 2; j++) {
        for (k = 0; k < 2; k++) {
          for (l = 0; l < 2; l++) {
            tmat[j][k] += pows[i][j][l] * rmat[l][k];
            tmat[j][k] %= 1000000007;
          }
        }
      }
      for (j = 0; j < 2; j++) {
        for (k = 0; k < 2; k++) rmat[j][k] = tmat[j][k], tmat[j][k] = 0;
      }
    }
  }
  return rmat[0][0];
}
void mod(long long &x) {
  x %= 1000000007;
  x += 1000000007;
  x %= 1000000007;
}
void ineq(long long y, long long x) {
  if (x == -1) return;
  mod(y);
  if (teq.find(x) == teq.end())
    teq[x] = y;
  else
    teq[x] += y;
  mod(teq[x]);
}
int main() {
  long long i, j, k;
  scanf("%I64d%I64d", &n, &m);
  eq[1] = 1;
  eq[2] = 1;
  if (n != 1) {
    eq[n + 1] = -calcfib(n + 1);
    eq[n + 2] = -calcfib(n);
  } else {
    eq[n + 1] += -calcfib(n + 1);
    eq[n + 2] = -calcfib(n);
  }
  mod(eq[n + 1]), mod(eq[n + 2]);
  for (i = 1; i <= m; i++) {
    for (map<long long, long long>::iterator it = eq.begin(); it != eq.end();
         it++) {
      ineq(it->first % 1000000007 * it->second % 1000000007, it->first);
      ineq(-it->first % 1000000007 * it->second % 1000000007, it->first + 1);
      ineq(-it->first % 1000000007 * it->second % 1000000007, it->first + 2);
      ineq((long long)i * it->second % 1000000007, it->first + 1);
      ineq((long long)2 * i * it->second % 1000000007, it->first + 2);
    }
    eq.clear();
    for (map<long long, long long>::iterator it = teq.begin(); it != teq.end();
         it++) {
      eq[it->first] = it->second;
    }
    teq.clear();
  }
  long long dab = 0;
  for (map<long long, long long>::iterator it = eq.begin(); it != eq.end();
       it++) {
    dab += it->second;
    mod(dab);
  }
  if (m % 2 == 0) dab = -dab, mod(dab);
  printf("%I64d", dab);
  return 0;
}