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;
using ll = long long;
namespace {
ll read() {
  ll x;
  cin >> x;
  return x;
}
string reads() {
  string s;
  cin >> s;
  return s;
}
void writeln() { cout << '\n'; }
template <class T, class... TS>
void writeln(T x, TS... xs) {
  cout << x << ' ';
  writeln(xs...);
}
template <class T>
void write(T x) {
  cout << x << ' ';
}
struct init {
  init() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} init_;
}  // namespace
const int MOD = 1000000007;
struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};
mint operator-(mint a) { return a.n == 0 ? 0 : MOD - a.n; }
mint operator+(mint a, mint b) {
  a.n += b.n;
  if (a.n >= MOD) a.n -= MOD;
  return a;
}
mint operator-(mint a, mint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += MOD;
  return a;
}
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }
vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};
void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}
mint I(int n) {
  check_fact(n);
  return I_[n];
}
mint F(int n) {
  check_fact(n);
  return n < 0 ? 0 : F_[n];
}
mint R(int n) {
  check_fact(n);
  return n < 0 ? 0 : R_[n];
}
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }
struct mint2 {
  mint x, y;
  mint2(int x_) : x(x_), y(0) {}
  mint2() : x(0), y(0) {}
  mint2(mint x_) : x(x_), y(0) {}
  mint2(mint x_, mint y_) : x(x_), y(y_) {}
};
mint2 operator-(mint2 a) { return mint2(-a.x, -a.y); }
mint2 operator+(mint2 a, mint2 b) {
  a.x += b.x;
  a.y += b.y;
  return a;
}
mint2 operator-(mint2 a, mint2 b) {
  a.x -= b.x;
  a.y -= b.y;
  return a;
}
mint2 operator*(mint2 a, mint2 b) {
  mint2 c;
  c.x = a.x * b.x + 5 * a.y * b.y;
  c.y = a.x * b.y + a.y * b.x;
  return c;
}
mint2 conj(mint2 a) { return mint2(a.x, -a.y); }
mint2 &operator+=(mint2 &a, mint2 b) { return a = a + b; }
mint2 &operator-=(mint2 &a, mint2 b) { return a = a - b; }
mint2 &operator*=(mint2 &a, mint2 b) { return a = a * b; }
mint2 modpow(mint2 a, long long b) {
  mint2 res;
  res.x = 1;
  while (b > 0) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}
mint modinv(mint n) {
  int a = n.n;
  int b = MOD;
  int s = 1;
  int t = 0;
  while (b != 0) {
    int q = a / b;
    a -= q * b;
    s -= q * t;
    swap(a, b);
    swap(s, t);
  }
  if (s < 0) s += MOD;
  return s;
}
mint2 modpowsum(mint2 a, long long b) {
  mint2 res = 0;
  mint2 s = 1;
  mint2 p = 1;
  while (b > 0) {
    if (b & 1) {
      res += s * p;
      p *= a;
    }
    s *= a + 1;
    a *= a;
    b >>= 1;
  }
  return res;
}
mint2 modinv(mint2 a) { return conj(a) * modinv(a.x * a.x - 5 * a.y * a.y); }
ostream &operator<<(ostream &o, mint2 a) { return o << a.x << ',' << a.y; }
int main() {
  long long N, K;
  cin >> N >> K;
  mint2 alpha = mint2(1, 1) * I(2);
  vector<mint2> S(K + 1);
  S[0] = modpowsum(alpha, N + 2) - 1 - alpha;
  for (int k = 1; k <= K; k++) {
    S[k] = alpha * alpha - modpow(alpha, N + 2) * modpow(N % MOD, k);
    for (int j = 0; j <= k - 1; j++) {
      S[k] += (S[j] - alpha * alpha) * modpow(MOD - 1, k - j + 1) * C(k, j);
    }
    S[k] *= modinv(1 - alpha);
  }
  mint2 ans = (S[K] - conj(S[K])) * mint2(0, I(5));
  writeln(ans.x);
}