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 = 100;
const int mod = 1e9 + 7;
void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}
int mult(int a, int b) { return (1ll * a * b) % mod; }
struct matrix {
  int n, m;
  int a[N][N];
  matrix(int _n = 0, int _m = 0) {
    n = _n;
    m = _m;
    memset(a, 0, sizeof a);
  }
  void out() {
    cout << n << " " << m << endl;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) cout << a[i][j] << " ";
      cout << endl;
    }
  }
};
long long n;
int k, cnk[N][N], first[N], pw[N];
matrix operator*(matrix a, matrix b) {
  matrix c(a.n, b.m);
  for (int i = 1; i <= c.n; i++)
    for (int j = 1; j <= c.m; j++)
      for (int k = 1; k <= a.m; k++) add(c.a[i][j], mult(a.a[i][k], b.a[k][j]));
  return c;
}
matrix bp(matrix a, long long n) {
  matrix ans(a.n, a.m);
  for (int i = 1; i <= a.n; i++) ans.a[i][i] = 1;
  while (n) {
    if (n & 1) ans = ans * a;
    a = a * a;
    n >>= 1;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  clock_t start = clock();
  cin >> n >> k;
  for (int i = 0; i <= k; i++) {
    cnk[i][0] = 1;
    for (int j = 1; j <= i; j++)
      cnk[i][j] = sum(cnk[i - 1][j], cnk[i - 1][j - 1]);
  }
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  pw[0] = 1;
  for (int i = 0; i <= k; i++) pw[i + 1] = sum(pw[i], pw[i]);
  matrix A(1, 2 * (k + 1) + 1);
  for (int i = 1; i <= k + 1; i++) A.a[1][i] = 1;
  for (int i = k + 2; i <= 2 * (k + 1); i++) A.a[1][i] = pw[i - (k + 1)];
  A.a[1][2 * (k + 1) + 1] = sum(A.a[1][2 * (k + 1)], A.a[1][k + 1]);
  matrix B(2 * (k + 1) + 1, 2 * (k + 1) + 1);
  for (int i = 1; i <= k + 1; i++) B.a[k + 1 + i][i] = 1;
  for (int i = k + 2; i <= 2 * (k + 1); i++) {
    int deg = i - (k + 2);
    for (int j = 0; j <= deg; j++) {
      B.a[j + 1][i] = mult(pw[deg - j], cnk[deg][j]);
      B.a[j + k + 2][i] = cnk[deg][j];
      if (i == 2 * (k + 1)) {
        B.a[j + 1][2 * (k + 1) + 1] = mult(pw[deg - j], cnk[deg][j]);
        B.a[j + k + 2][2 * (k + 1) + 1] = cnk[deg][j];
      }
    }
  }
  B.a[2 * (k + 1) + 1][2 * (k + 1) + 1] = 1;
  A = A * bp(B, n - 2);
  cout << A.a[1][2 * (k + 1) + 1];
  double duration = ((double)clock() - start) / (double)CLOCKS_PER_SEC;
  return 0;
}