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>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <typename T>
T ext_gcd(T a, T b, T& first, T& second) {
  if (b == 0) {
    first = 1, second = 0;
    return a;
  }
  T d = ext_gcd(b, a % b, second, first);
  second -= first * (a / b);
  return d;
}
template <typename T>
T inverse(T a, T n) {
  T first, second;
  T t = ext_gcd(a, n, first, second);
  if (t != 1) return -1;
  return (first % n + n) % n;
}
template <typename T>
T Q_mul(T a, T b, T Mod) {
  T ret;
  for (ret = 0; b; b >>= 1, a = (a + a) % Mod)
    if (b & 1) ret = (ret + a) % Mod;
  return ret;
}
template <typename T>
T quick_pow_mod(T a, T b, T Mod) {
  T ret;
  for (ret = 1; b; b >>= 1, (a *= a) %= Mod)
    if (b & 1) (ret *= a) %= Mod;
  return ret;
}
template <typename T>
T quick_pow(T a, T b) {
  T ret;
  for (ret = 1; b; b >>= 1, a *= a)
    if (b & 1) ret *= a;
  return ret;
}
double combination(int n, int r) {
  if (r < n - r) return combination(n, n - r);
  double s = 1.0;
  for (int i = 1; i <= int(n - r); ++i) s *= (r + i), s /= i;
  return s;
}
template <typename T>
inline void read(T& v) {
  T ret = 0, sgnv = 1;
  char p;
  while (!isdigit(p = getchar()))
    if (p == '-') sgnv = -1;
  do ret = (ret << 3) + (ret << 1) + p - '0';
  while (isdigit(p = getchar()));
  v = sgnv * ret;
}
const long long mod = 1000000007;
long long tmp[83][83];
struct Matrix {
  int n;
  long long v[83][83];
  void init() {
    for (int i = 0; i < int(n); ++i) v[i][i] = 1;
  }
  void operator*=(Matrix& r) {
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < int(n); ++i)
      for (int j = 0; j < int(n); ++j)
        if (v[i][j])
          for (int k = 0; k < int(n); ++k)
            (tmp[i][k] += v[i][j] * r.v[j][k] % mod) %= mod;
    for (int i = 0; i < int(n); ++i)
      for (int j = 0; j < int(n); ++j) v[i][j] = tmp[i][j];
  }
} ret, a;
int c[45][45];
int main() {
  long long n, ans = 0;
  for (int i = 0; i < int(41); ++i)
    for (int j = 0; j < int(i + 1); ++j) {
      c[i][0] = c[i][i] = 1;
      for (int j = int(1); j <= int(i - 1); ++j)
        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  int k;
  read(n), read(k), --n;
  a.n = ret.n = (k << 1) + 3, a.v[0][0] = 1;
  for (int j = 1; j <= int(k + 1); ++j)
    a.v[0][j] = a.v[0][a.n - j] = c[k][j - 1];
  for (int i = 1; i <= int(k + 1); ++i)
    for (int j = int(i); j <= int(k + 1); ++j)
      a.v[i][j] = a.v[i][a.n - 1 - j + i] = a.v[i + k + 1][j] =
          c[k + 1 - i][j - i];
  for (ret.init(); n; n >>= 1, a *= a)
    if (n & 1) ret *= a;
  for (int i = 0; i < int(a.n); ++i) ans = (ans + ret.v[0][i]) % mod;
  printf("%I64d", ans);
  return 0;
}