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 long long mod = (long long)1e9 + 7LL;
struct matrix {
  int m, n;
  int d[88][88];
  matrix() {
    m = 0;
    n = 0;
    memset(d, 0, sizeof d);
  }
  void assign(int x, int y) {
    m = x;
    n = y;
  }
  void operator=(const matrix &x) {
    m = x.m;
    n = x.n;
    for (int i = 0; i < (m); i = i + 1)
      for (int j = 0; j < (n); j = j + 1) d[i][j] = x.d[i][j];
  }
  matrix operator*(const matrix &a) const {
    matrix res;
    int x = m;
    int y = n;
    int z = a.n;
    res.m = x;
    res.n = z;
    for (int i = 0; i < (x); i = i + 1)
      for (int j = 0; j < (z); j = j + 1) {
        res.d[i][j] = 0;
        for (int k = 0; k < (y); k = k + 1)
          res.d[i][j] = (res.d[i][j] + 1LL * d[i][k] * a.d[k][j]) % mod;
      }
    return (res);
  }
  matrix operator^(long long k) const {
    assert(m == n);
    matrix res;
    matrix mul = *this;
    res.m = m;
    res.n = n;
    for (int i = 0; i < (m); i = i + 1)
      for (int j = 0; j < (n); j = j + 1) res.d[i][j] = (i == j);
    while (k > 0) {
      if (k % 2 == 1) res = res * mul;
      mul = mul * mul;
      k = k >> 1;
    }
    return (res);
  }
};
int k;
long long n;
int c[80][80];
matrix fst, mul;
void process(void) {
  cin >> n >> k;
  for (int i = (1); i <= (k + 3); i = i + 1) {
    c[i][0] = 0;
    c[0][i] = 1;
  }
  c[0][0] = 1;
  for (int i = (1); i <= (k + 3); i = i + 1)
    for (int j = (1); j <= (k + 3); j = j + 1) {
      if (i > j) c[i][j] = 0;
      if (i == j) c[i][j] = 1;
      if (i < j) c[i][j] = (c[i - 1][j - 1] + c[i][j - 1]) % mod;
    }
  fst.assign(1, 2 * k + 3);
  mul.assign(2 * k + 3, 2 * k + 3);
  for (int i = 0; i < (k + 1); i = i + 1)
    for (int j = 0; j < (k + 1); j = j + 1) mul.d[i][j] = 0;
  for (int i = 0; i < (k + 1); i = i + 1)
    for (int j = (k + 1); j <= (2 * k + 1); j = j + 1) {
      int j1 = j - k - 1;
      if (i > j1)
        mul.d[i][j] = 0;
      else
        mul.d[i][j] = c[i][j1];
    }
  for (int i = (k + 1); i <= (2 * k + 1); i = i + 1)
    for (int j = 0; j < (k + 1); j = j + 1) {
      int i1 = i - k - 1;
      if (i1 > j)
        mul.d[i][j] = 0;
      else
        mul.d[i][j] = c[i1][j];
    }
  for (int i = (k + 1); i <= (2 * k + 1); i = i + 1)
    for (int j = (k + 1); j <= (2 * k + 1); j = j + 1) {
      int i1 = i - k - 1;
      int j1 = j - k - 1;
      if (i1 > j1)
        mul.d[i][j] = 0;
      else
        mul.d[i][j] = c[i1][j1];
    }
  for (int i = 0; i < (2 * k + 3); i = i + 1) {
    mul.d[2 * k + 2][i] = 0;
    mul.d[i][2 * k + 2] = 0;
  }
  mul.d[2 * k + 2][2 * k + 2] = 1;
  mul.d[2 * k + 1][2 * k + 2] = 1;
  for (int i = 0; i < (2 * k + 2); i = i + 1) fst.d[0][i] = 1;
  fst.d[0][2 * k + 2] = 0;
  fst = fst * (mul ^ n);
  cout << fst.d[0][2 * k + 2];
}
int main(void) {
  process();
  return 0;
}