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;
template <typename T>
int read(T &x) {
  x = 0;
  T f = 1;
  char tem = getchar();
  while (tem < '0' || tem > '9') {
    if (tem == '-') f = -1;
    tem = getchar();
  }
  while (tem >= '0' && tem <= '9') {
    x = (x << 1) + (x << 3) + tem - '0';
    tem = getchar();
  }
  x *= f;
  return 1;
}
template <typename T>
void write(T x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
T Max(T x, T y) {
  return x > y ? x : y;
}
template <typename T>
T Min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T Abs(T x) {
  return x > 0 ? x : -x;
}
const int Maxn = 100;
const long long Mod = 1e9 + 7;
struct Matrix {
  int n, m;
  long long c[Maxn * 2 + 5][Maxn * 2 + 5];
  Matrix() { memset(c, 0, sizeof c); }
  void init() {
    for (int i = 0; i <= n; i++) c[i][i] = 1;
  }
  void cpy(long long a[][Maxn + 5]) {
    for (int i = 0; i < Maxn + 5; i++) {
      for (int j = 0; j < Maxn + 5; j++) {
        c[i][j] = a[i][j];
      }
    }
  }
  void read() {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        scanf("%lld", &c[i][j]);
        c[i][j] %= Mod;
        if (c[i][j] < 0) c[i][j] += Mod;
      }
    }
  }
  void write() {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        printf("%lld ", c[i][j]);
      }
      puts("");
    }
  }
  Matrix operator*(const Matrix x) const {
    Matrix ans;
    ans.n = n;
    ans.m = x.m;
    for (int i = 1; i <= ans.n; i++) {
      for (int k = 1; k <= m; k++) {
        for (int j = 1; j <= ans.m; j++) {
          ans.c[i][j] += c[i][k] * x.c[k][j];
          ans.c[i][j] %= Mod;
          if (ans.c[i][j] < 0) ans.c[i][j] += Mod;
        }
      }
    }
    return ans;
  }
  Matrix operator+(const Matrix x) const {
    Matrix ans;
    ans.n = n;
    ans.m = m;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        ans.c[i][j] = c[i][j] + x.c[i][j];
      }
    }
    return ans;
  }
  Matrix operator-(const Matrix x) const {
    Matrix ans;
    ans.n = n;
    ans.m = m;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        ans.c[i][j] = c[i][j] + x.c[i][j];
      }
    }
    return ans;
  }
};
long long fac[Maxn + 5], inv_fac[Maxn + 5];
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
long long inv(long long a) {
  long long x, y;
  exgcd(a, Mod, x, y);
  x = ((x % Mod) + Mod) % Mod;
  return x;
}
void Init() {
  fac[0] = 1;
  for (int i = 1; i <= Maxn; i++) {
    fac[i] = fac[i - 1] * i;
    fac[i] %= Mod;
  }
  inv_fac[Maxn] = inv(fac[Maxn]);
  for (int i = Maxn - 1; i >= 0; i--) {
    inv_fac[i] = inv_fac[i + 1] * (i + 1) % Mod;
  }
}
long long C(long long a, long long b) {
  if (b == 0) return 1;
  return fac[b] * inv_fac[a] % Mod * inv_fac[b - a] % Mod;
}
long long n;
int k;
long long quick_pow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % Mod;
    a = (a * a) % Mod;
    b >>= 1;
  }
  return res;
}
Matrix quick_pow(Matrix a, long long b) {
  Matrix res;
  res.n = res.m = a.n;
  res.init();
  while (b) {
    if (b & 1) res = (res * a);
    a = (a * a);
    b >>= 1;
  }
  return res;
}
int main() {
  read(n);
  read(k);
  Init();
  Matrix a, b;
  a.n = 1;
  a.m = b.n = b.m = 2 * k + 3;
  a.c[1][2 * k + 3] = 0;
  for (int i = 1; i <= k + 1; i++) a.c[1][i] = 1;
  for (int i = k + 2; i <= 2 * k + 2; i++)
    a.c[1][i] = 2 * quick_pow(2, i - k - 2);
  for (int j = 1; j <= k + 1; j++) {
    b.c[j + k + 1][j] = 1;
  }
  for (int j = k + 2; j <= 2 * k + 2; j++) {
    for (int i = 1; i <= j - k - 1; i++) {
      b.c[i][j] = quick_pow(2, j - k - 1 - i) * C(i - 1, j - k - 2) % Mod;
    }
    for (int i = k + 2; i <= j; i++) {
      b.c[i][j] = C(i - k - 2, j - k - 2);
    }
  }
  b.c[2 * k + 3][2 * k + 3] = b.c[2 * k + 2][2 * k + 3] = 1;
  a = a * quick_pow(b, n - 1);
  printf("%lld", a.c[1][2 * k + 3] + 1);
  return 0;
}