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;
constexpr int kMod = int(1E9 + 7), kN = int(100);
template <typename T>
T Pow(T a, long long int b) {
  T ans(1);
  while (b) {
    if (b & 1) ans *= a;
    a *= a;
    b >>= 1;
  }
  return ans;
}
template <int kMod>
struct Mod_Int {
  long long int val;
  Mod_Int() { val = 0; }
  Mod_Int(long long int x) { val = x; }
  Mod_Int inv() const { return Pow(*this, kMod - 2); }
  Mod_Int operator+(const Mod_Int x) const {
    Mod_Int ans(val + x.val);
    if (ans.val >= kMod) ans.val -= kMod;
    return ans;
  }
  Mod_Int operator-(const Mod_Int x) const {
    Mod_Int ans(val - x.val);
    if (ans.val < 0) ans.val += kMod;
    return ans;
  }
  Mod_Int operator*(const Mod_Int x) const {
    return Mod_Int(val * x.val % kMod);
  }
  Mod_Int operator/(const Mod_Int x) const { return *this * x.inv(); }
  Mod_Int operator+=(const Mod_Int x) {
    val += x.val;
    if (val >= kMod) val -= kMod;
    return *this;
  }
  Mod_Int operator-=(const Mod_Int x) {
    val -= x.val;
    if (val < 0) val += kMod;
    return *this;
  }
  Mod_Int operator*=(const Mod_Int x) {
    val = val * x.val % kMod;
    return *this;
  }
  Mod_Int operator/=(const Mod_Int x) {
    val = *this * x.inv();
    return *this;
  }
  bool operator==(const Mod_Int x) const { return val == x.val; }
  bool operator!=(const Mod_Int x) const { return val != x.val; }
};
namespace Factorial {
vector<Mod_Int<kMod> > f;
vector<Mod_Int<kMod> > inf;
void Pre_Factorial(int sz) {
  f.resize(sz), inf.resize(sz);
  f[0] = f[1] = inf[0] = inf[1] = 1;
  for (int i = 2; i < sz; i++) f[i] = f[i - 1] * i;
  inf[sz - 1] = f[sz - 1].inv();
  for (int i = sz - 1; i > 2; i--) inf[i - 1] = inf[i] * i;
}
Mod_Int<kMod> P(int n, int m) { return f[n] * inf[m]; }
Mod_Int<kMod> C(int n, int m) { return f[n] * inf[m] * inf[n - m]; }
Mod_Int<kMod> H(int n, int m) { return f[n + m - 1] * inf[m] * inf[n - 1]; }
}  // namespace Factorial
namespace No_Inf_Factorial {
vector<Mod_Int<kMod> > f;
void Pre_Factorial(int sz) {
  f.resize(sz);
  f[0] = f[1] = 1;
  for (int i = 2; i < sz; i++) f[i] = f[i - 1] * i;
  return;
}
Mod_Int<kMod> P(int n, int m) { return f[n] / f[m]; }
Mod_Int<kMod> C(int n, int m) { return f[n] / (f[m] * f[n - m]); }
Mod_Int<kMod> H(int n, int m) { return f[n + m - 1] / (f[m] * f[n - 1]); }
}  // namespace No_Inf_Factorial
struct Matrix {
  Mod_Int<kMod> val[kN][kN];
  Matrix() { memset(val, 0, sizeof(val)); }
  void operator*=(Matrix a) {
    long long int tmp[kN][kN];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < kN; i++)
      for (int j = 0; j < kN; j++)
        for (int k = 0; k < kN; k++) tmp[i][j] += (val[i][k] * a.val[k][j]).val;
    for (int i = 0; i < kN; i++)
      for (int j = 0; j < kN; j++) val[i][j] = tmp[i][j] % kMod;
    return;
  }
};
Matrix Pow(Matrix a, long long int b) {
  Matrix ans;
  for (int i = 0; i < kN; i++) ans.val[i][i] = 1;
  while (b) {
    if (b & 1) ans *= a;
    b >>= 1;
    a *= a;
  }
  return ans;
}
using namespace Factorial;
int main() {
  Pre_Factorial(kN);
  long long int n, k, tmp;
  Matrix A, ans;
  scanf("%lld%lld", &n, &k);
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= i; j++) A.val[k - i][k - j] = C(i, j);
  for (int i = 0; i <= k; i++)
    for (int j = k + 1; j <= k * 2 + 1; j++) A.val[i][j] = A.val[i][j - k - 1];
  for (int i = k + 1; i <= k * 2 + 1; i++)
    for (int j = 0; j <= k; j++) A.val[i][j] = A.val[i - k - 1][j];
  A.val[k * 2 + 2][0] = A.val[k * 2 + 2][k * 2 + 2] = 1;
  ans = Pow(A, n);
  tmp = 0;
  for (int i = 0; i < k * 2 + 2; i++) tmp += ans.val[k * 2 + 2][i].val;
  printf("%lld\n", tmp % kMod);
}