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;
const ll mod = 1e9 + 7;
ll ipow(ll x, ll p) {
  ll ret = 1, piv = x;
  while (p) {
    if (p & 1) ret = ret * piv % mod;
    piv = piv * piv % mod;
    p >>= 1;
  }
  return ret;
}
vector<ll> berlekamp_massey(vector<ll> x) {
  vector<ll> ls, cur;
  int lf, ld;
  for (int i = 0; i < x.size(); i++) {
    ll t = 0;
    for (int j = 0; j < cur.size(); j++) {
      t = (t + 1ll * x[i - j - 1] * cur[j]) % mod;
    }
    if ((t - x[i]) % mod == 0) continue;
    if (cur.empty()) {
      cur.resize(i + 1);
      lf = i;
      ld = (t - x[i]) % mod;
      continue;
    }
    ll k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
    vector<ll> c(i - lf - 1);
    c.push_back(k);
    for (auto &j : ls) c.push_back(-j * k % mod);
    if (c.size() < cur.size()) c.resize(cur.size());
    for (int j = 0; j < cur.size(); j++) {
      c[j] = (c[j] + cur[j]) % mod;
    }
    if (i - lf + (int)ls.size() >= (int)cur.size()) {
      tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod);
    }
    cur = c;
  }
  for (auto &i : cur) i = (i % mod + mod) % mod;
  return cur;
}
int get_nth(vector<ll> rec, vector<ll> dp, ll n) {
  int m = rec.size();
  vector<ll> s(m), t(m);
  s[0] = 1;
  if (m != 1)
    t[1] = 1;
  else
    t[0] = rec[0];
  auto mul = [&rec](vector<ll> v, vector<ll> w) {
    int m = v.size();
    vector<ll> t(2 * m);
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < m; k++) {
        t[j + k] += 1ll * v[j] * w[k] % mod;
        if (t[j + k] >= mod) t[j + k] -= mod;
      }
    }
    for (int j = 2 * m - 1; j >= m; j--) {
      for (int k = 1; k <= m; k++) {
        t[j - k] += 1ll * t[j] * rec[k - 1] % mod;
        if (t[j - k] >= mod) t[j - k] -= mod;
      }
    }
    t.resize(m);
    return t;
  };
  while (n) {
    if (n & 1) s = mul(s, t);
    t = mul(t, t);
    n >>= 1;
  }
  ll ret = 0;
  for (int i = 0; i < m; i++) ret = (ret + s[i] * dp[i]) % mod;
  return ret;
}
ll guess_nth_term(vector<ll> x, ll n) {
  if (n < x.size()) return x[n];
  vector<ll> v = berlekamp_massey(x);
  if (v.empty()) return 0;
  return get_nth(v, x, n);
}
ll n, k, dp[1010];
vector<ll> v;
ll f(ll a, ll b) {
  ll re = 1;
  for (int i = 1; i <= b; i++) re = (re * a) % mod;
  return re;
}
int main() {
  scanf("%lld %lld", &n, &k);
  dp[1] = 1, dp[2] = 2;
  for (int i = 3; i <= 1000; i++) dp[i] = (dp[i - 2] + dp[i - 1]) % mod;
  ll s = 0;
  for (int i = 1; i <= 1000; i++) {
    s = (s + dp[i] * f(i, k)) % mod;
    v.push_back(s);
  }
  printf("%lld", guess_nth_term(v, n - 1));
}