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 MOD = 1e9 + 7;
const int N = 85;
struct Matrix {
  long long c[N + 1][N + 1];
  Matrix() { memset(c, 0, sizeof(c)); }
  Matrix operator*(const Matrix &rhs) const {
    Matrix r;
    for (int i = int(0); i <= int(N); ++i)
      for (int k = int(0); k <= int(N); ++k)
        for (int j = int(0); j <= int(N); ++j) {
          r.c[i][j] += c[i][k] * rhs.c[k][j] % MOD;
          if (r.c[i][j] >= MOD) r.c[i][j] -= MOD;
        }
    return r;
  }
  Matrix operator^(long long b) {
    Matrix r;
    Matrix a = (*this);
    for (int i = int(0); i <= int(N); ++i) r.c[i][i] = 1;
    while (b) {
      if (b & 1) r = r * a;
      a = a * a;
      b >>= 1;
    }
    return r;
  }
} O;
long long C[101][101], pw[101];
int main() {
  C[0][0] = 1;
  for (int i = int(1); i <= int(100); ++i) {
    C[i][0] = 1;
    for (int j = int(1); j <= int(i); ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
  pw[0] = 1LL;
  for (int i = int(1); i <= int(100); ++i) pw[i] = pw[i - 1] * 2 % MOD;
  long long n, k;
  cin >> n >> k;
  for (int i = int(0); i <= int(k); ++i) O.c[i + 1 + k][i] = 1;
  for (int i = int(k + 1); i <= int(2 * k + 1); ++i) {
    for (int j = int(0); j <= int(i - k - 1); ++j)
      O.c[j][i] = C[i - k - 1][j] * pw[i - k - 1 - j] % MOD;
    for (int j = int(0); j <= int(i - k - 1); ++j)
      O.c[j + k + 1][i] = C[i - k - 1][j];
  }
  O.c[2 * k + 1][2 * k + 2] = O.c[2 * k + 2][2 * k + 2] = 1;
  O = O ^ n;
  long long ans = O.c[0][2 * k + 2];
  for (int i = int(k + 1); i <= int(2 * k + 1); ++i) {
    ans += O.c[i][2 * k + 2];
    if (ans >= MOD) ans -= MOD;
  }
  cout << ans << endl;
}