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 long long mod = 1e9 + 7;
long long C[110][110];
void init() {
  memset(C, 0, sizeof(C));
  C[0][0] = 1;
  for (int i = 1; i < 100; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
}
struct matrix {
  long long jie[110][110];
  long long n, m;
  void init() {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j) jie[i][j] = 0;
  }
  matrix operator*(const matrix &a) const {
    matrix b;
    b.n = n;
    b.m = a.m;
    b.init();
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= a.m; ++j) {
        b.jie[i][j] = 0;
        for (int k = 1; k <= m; ++k) {
          b.jie[i][j] = ((jie[i][k] * a.jie[k][j]) % mod + b.jie[i][j]) % mod;
        }
      }
    return b;
  }
} t1, t2, t3;
matrix mpow(matrix a, long long b) {
  matrix kk;
  kk.n = kk.m = a.n;
  kk = a;
  b--;
  while (b) {
    if (b & 1) kk = kk * a;
    a = a * a;
    b >>= 1;
  }
  return kk;
}
long long n, m;
void gao() {
  t1.n = 2 * m + 3;
  t1.m = 1;
  t1.init();
  for (int i = 1; i <= t1.n - 1; ++i) t1.jie[i][1] = 1;
  t1.jie[t1.n][1] = 0;
  t2.n = t2.m = 2 * m + 3;
  t2.init();
  for (int i = 1; i <= m + 1; ++i) {
    for (int j = 1; j <= i; ++j) {
      t2.jie[i][j] = t2.jie[i + 1 + m][j] = t2.jie[i][1 + m + j] =
          C[i - 1][j - 1];
    }
  }
  t2.jie[2 * m + 3][1 + m] = 1;
  t2.jie[2 * m + 3][2 * m + 3] = 1;
}
int main() {
  init();
  scanf("%lld%lld", &n, &m);
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  gao();
  t3 = mpow(t2, n - 1) * t1;
  long long ans = 0;
  ans = (t3.jie[m + 1][1] % mod + t3.jie[m * 2 + 3][1] % mod + mod) % mod;
  printf("%lld\n", ans);
  return 0;
}