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 long long mod = 1e9 + 7;
const long long maxn = 105;
struct Matrix {
  long long n, m;
  long long c[maxn][maxn];
  Matrix(long long N = 0, long long M = 0) {
    n = N, m = M;
    memset(c, 0, sizeof(c));
  }
  Matrix operator*(const Matrix a) const {
    long long l = n, r = a.m;
    Matrix x = Matrix(l, r);
    for (long long i = 1; i <= l; ++i) {
      for (long long j = 1; j <= r; ++j) {
        for (long long k = 1; k <= m; ++k) {
          x.c[i][j] += c[i][k] * a.c[k][j];
          x.c[i][j] %= mod;
        }
      }
    }
    return x;
  }
} A, B;
long long n, k, x = 4;
long long f[45][45];
Matrix pow(Matrix& x, long long b) {
  Matrix ans = Matrix(x.n, x.m);
  for (long long i = 1; i <= x.m; ++i) ans.c[i][i] = 1;
  while (b) {
    if (b & 1) ans = x * ans;
    x = x * x;
    b >>= 1;
  }
  return ans;
}
inline void init(void) {
  f[0][0] = 1;
  for (long long i = 1; i <= k; ++i) {
    f[i][0] = 1;
    for (long long j = 1; j <= i; ++j)
      f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
  }
  return;
}
signed main() {
  scanf("%lld%lld", &n, &k);
  init();
  A = Matrix(1, 3 + (k << 1));
  A.c[1][1] = 1;
  A.c[1][2] = 2;
  A.c[1][3] = 1;
  for (long long i = 1; i <= k; ++i) {
    A.c[1][3 + i] = 1;
    A.c[1][k + 3 + i] = x % mod;
    x <<= 1;
  }
  B = Matrix(3 + (k << 1), 3 + (k << 1));
  B.c[2][1] = 1;
  B.c[1][2] = B.c[2][2] = 1;
  B.c[3][3] = B.c[3 + (k << 1)][3] = 1;
  for (long long i = 1; i <= k; ++i) {
    B.c[1][i + k + 3] = (1ll << i) % mod;
    B.c[3 + k + i][3 + i] = 1;
    B.c[2][3 + i + k] = 1;
  }
  for (long long i = 1; i <= k; ++i) {
    for (long long j = i; j <= k; ++j) {
      B.c[3 + i][3 + k + j] = (((1ll << j - i) % mod) * f[j][i]) % mod;
      B.c[3 + k + i][3 + k + j] = f[j][i];
    }
  }
  A = A * pow(B, n - 1);
  printf("%lld", A.c[1][3]);
  return 0;
}