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;
long long mod = 1e9 + 7;
struct getinv {
 private:
  void extend_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return;
    }
    extend_gcd(b, a % b, x, y);
    long long tmp = x;
    x = y;
    y = tmp - (a / b) * y;
  }

 public:
  long long mod_inv(long long a, long long m = mod) {
    long long x, y;
    extend_gcd(a, m, x, y);
    return (m + x % m) % m;
  }
} inv;
struct node {
  long long n, m;
  long long val[100][100];
  node() { memset(val, 0, sizeof val); }
  node operator*(const node& o) const {
    node ans;
    ans.n = n;
    ans.m = o.m;
    for (long long i = 1; i <= ans.n; i++) {
      for (long long j = 1; j <= ans.m; j++) {
        ans.val[i][j] = 0;
        for (long long k = 1; k <= m; k++) {
          ans.val[i][j] += val[i][k] * o.val[k][j];
          ans.val[i][j] %= mod;
        }
      }
    }
    return ans;
  }
};
node qpow(node& o, long long n) {
  node base = o;
  node ans;
  ans.n = ans.m = o.m;
  for (long long i = 1; i <= ans.n; i++) {
    ans.val[i][i] = 1;
  }
  while (n) {
    if (n & 1) ans = ans * base;
    base = base * base;
    n /= 2;
  }
  return ans;
}
long long qpow(long long a, long long n) {
  long long base = a;
  long long ans = 1;
  while (n) {
    if (n & 1) ans = ans * base, ans %= mod;
    base = base * base;
    base %= mod;
    n /= 2;
  }
  return ans;
}
long long f[100];
long long fi[100];
inline long long C(long long a, long long b) {
  long long ans = f[a];
  ans *= inv.mod_inv(f[b]);
  ans %= mod;
  ans *= inv.mod_inv(f[a - b]);
  ans %= mod;
  return ans;
}
signed main() {
  long long n, k;
  cin >> n >> k;
  f[0] = 1;
  fi[1] = 1;
  fi[0] = 1;
  for (long long i = 1; i < 100; i++) {
    f[i] = f[i - 1] * i;
    f[i] %= mod;
  }
  for (long long i = 2; i < 100; i++) fi[i] = (fi[i - 1] + fi[i - 2]) % mod;
  node zhuanyi;
  node ans;
  zhuanyi.m = zhuanyi.n = 83;
  ans.n = 1;
  ans.m = 83;
  for (long long nowk = 0; nowk <= 40; nowk++) {
    long long lie = nowk + 1;
    for (long long j = 0; j <= nowk; j++) {
      long long v = C(nowk, j);
      zhuanyi.val[j + 1][lie] = v;
    }
    for (long long j = 0; j <= nowk; j++) {
      long long v = ((C(nowk, j)) % mod * qpow(2, nowk - j)) % mod;
      zhuanyi.val[j + 42][lie] = v;
    }
  }
  for (long long nowk = 42; nowk <= 82; nowk++) {
    zhuanyi.val[nowk - 41][nowk] = 1;
  }
  zhuanyi.val[83][83] = 1;
  zhuanyi.val[42 + k][83] = 1;
  for (long long nowk = 0; nowk <= 40; nowk++) {
    ans.val[1][nowk + 1] = 2 * qpow(2, nowk);
  }
  for (long long nowk = 0; nowk <= 40; nowk++) {
    ans.val[1][nowk + 42] = qpow(1, nowk);
  }
  ans.val[1][83] = 0;
  zhuanyi = qpow(zhuanyi, n);
  ans = ans * zhuanyi;
  cout << ans.val[1][83] << endl;
  return 0;
}