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 MAXN = 85;
struct matrix {
  int adj[MAXN][MAXN];
  int n;
  matrix(int _n, int c) {
    n = _n;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        adj[i][j] = (i == j ? c : 0);
      }
    }
  }
  matrix operator*(const matrix &a) const {
    matrix c(n, 0);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          c.adj[j][k] += 1ll * adj[j][i] * a.adj[i][k] % mod;
          c.adj[j][k] %= mod;
        }
      }
    }
    return c;
  }
  matrix operator+(const matrix &a) const {
    matrix c(n, 0);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        c.adj[i][j] = (adj[i][j] + a.adj[i][j]) % mod;
      }
    }
    return c;
  }
  matrix operator-(const matrix &a) const {
    matrix c(n, 0);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        c.adj[i][j] = (adj[i][j] + mod - a.adj[i][j]) % mod;
      }
    }
    return c;
  }
};
long long bino[44][44];
long long n, k;
int main() {
  cin >> n >> k;
  for (int i = 0; i <= k; i++) {
    bino[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      bino[i][j] = (bino[i - 1][j - 1] + bino[i - 1][j]) % mod;
    }
  }
  matrix ret(2 * k + 2, 0), piv(2 * k + 2, 0);
  for (int i = 0; i <= k; i++) {
    for (int j = i; j <= k; j++) {
      piv.adj[i][j] = bino[k - i][j - i];
      piv.adj[i][j + k + 1] =
          bino[k - i][j - i] * ((1ll << (j - i)) % mod) % mod;
    }
  }
  for (int i = 0; i <= k; i++) {
    piv.adj[i + k + 1][i] = 1;
  }
  matrix sum(2 * k + 2, 1), up(2 * k + 2, 1);
  for (int i = 0; i < 60; i++) {
    if ((n >> i) & 1) {
      ret = ret + sum * up;
      up = up * piv;
    }
    sum = sum + sum * piv;
    piv = piv * piv;
  }
  int dap = ret.adj[0][2 * k + 1];
  for (int i = 0; i <= k; i++) {
    dap += ret.adj[0][i];
    dap %= mod;
  }
  cout << dap;
}