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>
const int maxk = 50, maxm = maxk << 1;
const long long p = 1000000007;
long long n, k, m, C[maxk][maxk];
struct _matrix {
  long long num[maxm][maxm];
} E, trans;
inline _matrix matmul(_matrix A, _matrix B) {
  _matrix ans;
  for (int i = 0; i <= m; i++)
    for (int j = 0; j <= m; j++) {
      ans.num[i][j] = 0;
      for (int o = 0; o <= m; o++)
        ans.num[i][j] = (ans.num[i][j] + A.num[i][o] * B.num[o][j] % p) % p;
    }
  return ans;
}
_matrix qpow(_matrix A, long long r) {
  _matrix ans = E;
  for (_matrix t = A; r; r >>= 1, t = matmul(t, t))
    if (r & 1) ans = matmul(ans, t);
  return ans;
}
int main() {
  scanf("%I64d%I64d", &n, &k);
  m = ((k + 1) << 1) + 1 - 1;
  for (int i = 0; i <= k; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
  }
  for (int i = 0; i <= m; i++) E.num[i][i] = 1;
  trans.num[0][0] = trans.num[1][0] = 1;
  for (int i = 1; i <= k + 1; i++)
    for (int j = i; j <= k + 1; j++)
      trans.num[j][i] = trans.num[j + k + 1][i] = trans.num[j][i + k + 1] =
          C[k - i + 1][k - j + 1];
  _matrix res = qpow(trans, n);
  long long ans = 0;
  for (int i = 1; i <= m; i++) ans = (ans + res.num[i][0]) % p;
  printf("%I64d\n", ans);
  return 0;
}