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>
struct Polynomial {
  T v[256];
  int sz;
  static int mod;
  Polynomial() : sz(0) {}
  Polynomial(int n, const T &x = 0) : sz(n) { fill(v, v + n, x); }
  static void setMod(int p) { mod = p; }
  int size() const { return sz; }
  void resize(int n) { sz = n; }
  T &operator[](int k) { return v[k]; }
  Polynomial operator*(const Polynomial &o) const {
    Polynomial ret(sz + o.sz - 1);
    int i, j;
    for (i = 0; i < sz; ++i) {
      if (!v[i]) continue;
      for (j = 0; j < o.sz; ++j) {
        ret.v[i + j] += v[i] * o.v[j];
        if (~mod) ret.v[i + j] %= mod;
      }
    }
    return ret;
  }
  Polynomial operator%(const Polynomial &o) const {
    Polynomial ret = *this;
    int i, j, n = o.size() - 1;
    for (i = sz - 1; i >= n; --i) {
      if (!ret.v[i]) continue;
      for (j = 1; j <= n; ++j) {
        ret.v[i - j] -= ret.v[i] * o.v[n - j];
        if (~mod && (ret.v[i - j] %= mod) < 0) ret.v[i - j] += mod;
      }
    }
    ret.sz = min(ret.sz, n);
    return ret;
  }
  Polynomial pow(long long n, const Polynomial &p) const {
    Polynomial cur = *this, ret(1, 1);
    for (; n; n >>= 1) {
      if (n & 1) ret = (ret * cur) % p;
      cur = (cur * cur) % p;
    }
    return ret;
  }
};
template <typename T>
int Polynomial<T>::mod = -1;
Polynomial<long long> p, a;
long long sum[256], f[256];
long long modPow(long long a, long long b, long long p = 1000000007) {
  long long ret = 1;
  for (a %= p; b; b >>= 1) {
    if (b & 1) ret = (ret * a) % p;
    a = (a * a) % p;
  }
  return ret;
}
long long solve(long long n, int k) {
  int i, j, m = 2 * k + 3;
  long long ret = 0;
  if (n == 1) return 1;
  sum[0] = 0;
  sum[1] = 1;
  f[0] = f[1] = 1;
  for (i = 2; i <= m; ++i) {
    f[i] = (f[i - 1] + f[i - 2]) % 1000000007;
    sum[i] = (sum[i - 1] + f[i] * modPow(i, k)) % 1000000007;
    if (i == n) return sum[i];
  }
  p.resize(2);
  p[0] = 1000000007 - 1;
  p[1] = 1;
  a.resize(3);
  a[0] = 1000000007 - 1;
  a[1] = 1000000007 - 1;
  a[2] = 1;
  for (i = 0; i <= k; ++i) p = p * a;
  a.resize(2);
  a[0] = 0;
  a[1] = 1;
  a = a.pow(n, p);
  for (i = 0; i < a.size(); ++i) ret = (ret + a[i] * sum[i]) % 1000000007;
  return ret;
}
int main() {
  long long n;
  int k, i;
  Polynomial<long long>::setMod(1000000007);
  while (cin >> n >> k) {
    cout << solve(n, k) << endl;
  }
  return 0;
}