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;
const int MOD = 1e9 + 7;
struct berlekamp_massey {
  static const int SZ = 2e5 + 5;
  long long int m, a[SZ], h[SZ], t_[SZ], s[SZ], t[SZ];
  inline long long int bigmod(long long int b, long long int p,
                              long long int mod) {
    long long int res = 1 % mod, x = b % mod;
    while (p) {
      if (p & 1) res = (res * x) % mod;
      x = (x * x) % mod;
      p >>= 1;
    }
    return (res % mod);
  }
  inline vector<int> BM(vector<int> x) {
    vector<int> ls, cur;
    int lf, ld;
    for (int i = 0; i < int(x.size()); ++i) {
      long long int t = 0;
      for (int j = 0; j < int(cur.size()); ++j)
        t = (t + x[i - j - 1] * (1LL) * cur[j]) % MOD;
      if ((t - x[i]) % MOD == 0) continue;
      if (!cur.size()) {
        cur.resize(i + 1);
        lf = i;
        ld = (t - x[i]) % MOD;
        continue;
      }
      long long int k = -(x[i] - t) * bigmod(ld, MOD - 2, MOD) % MOD;
      vector<int> c(i - lf - 1);
      c.push_back(k);
      for (int j = 0; j < int(ls.size()); ++j) c.push_back(-ls[j] * k % MOD);
      if (c.size() < cur.size()) c.resize(cur.size());
      for (int j = 0; j < int(cur.size()); ++j) c[j] = (c[j] + cur[j]) % MOD;
      if (i - lf + (int)ls.size() >= (int)cur.size())
        ls = cur, lf = i, ld = (t - x[i]) % MOD;
      cur = c;
    }
    for (int i = 0; i < int(cur.size()); ++i)
      cur[i] = (cur[i] % MOD + MOD) % MOD;
    return cur;
  }
  inline void mull(long long int* p, long long int* q) {
    for (int i = 0; i < m + m; ++i) t_[i] = 0;
    for (int i = 0; i < m; ++i)
      if (p[i])
        for (int j = 0; j < m; ++j) t_[i + j] = (t_[i + j] + p[i] * q[j]) % MOD;
    for (int i = m + m - 1; i >= m; --i)
      if (t_[i])
        for (int j = m - 1; ~j; --j)
          t_[i - j - 1] = (t_[i - j - 1] + t_[i] * h[j]) % MOD;
    for (int i = 0; i < m; ++i) p[i] = t_[i];
  }
  inline long long int calc(long long int K) {
    for (int i = m; ~i; --i) s[i] = t[i] = 0;
    s[0] = 1;
    if (m != 1)
      t[1] = 1;
    else
      t[0] = h[0];
    while (K) {
      if (K & 1) mull(s, t);
      mull(t, t);
      K >>= 1;
    }
    long long int su = 0;
    for (int i = 0; i < m; ++i) su = (su + s[i] * a[i]) % MOD;
    return (su % MOD + MOD) % MOD;
  }
  inline int work(vector<int> x, long long int n) {
    if (n < int(x.size())) return x[n];
    vector<int> v = BM(x);
    m = v.size();
    if (!m) return 0;
    for (int i = 0; i < m; ++i) h[i] = v[i], a[i] = x[i];
    return calc(n);
  }
} rec;
long long int f[2000];
long long int a[2000];
long long int sum[2000];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  f[1] = 1, f[2] = 2;
  for (int i = 3; i <= 1000; i++)
    f[i] = (f[i - 1] % MOD + f[i - 2] % MOD) % MOD;
  long long int n, k;
  cin >> n >> k;
  vector<int> V;
  for (int i = 1; i <= 1000; i++)
    a[i] = (f[i] % MOD * rec.bigmod(i, k, MOD) % MOD) % MOD;
  for (int i = 1; i <= 1000; i++) {
    sum[i] = (sum[i - 1] % MOD + a[i] % MOD) % MOD;
    V.push_back(sum[i]);
  }
  cout << rec.work(V, n - 1) << endl;
  return 0;
}