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 INF = INT_MAX;
const long long INFL = LLONG_MAX;
const long double pi = acos(-1);
const int MOD = 1e9 + 7;
inline int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
inline int mul(int a, int b) {
  long long x = a * 1ll * b;
  x %= MOD;
  return (int)x;
}
vector<vector<int> > mul(vector<vector<int> > m1, vector<vector<int> > m2) {
  int p = int(m1.size());
  int q = int(m1[0].size());
  int r = int(m2[0].size());
  vector<vector<int> > ret(p, vector<int>(r));
  for (int(i) = 0, j123 = p; (i) < j123; (i)++)
    for (int(j) = 0, j123 = r; (j) < j123; (j)++)
      for (int(k) = 0, j123 = q; (k) < j123; (k)++)
        ret[i][j] = add(ret[i][j], mul(m1[i][k], m2[k][j]));
  return ret;
}
vector<vector<int> > mypow(vector<vector<int> > m, long long n) {
  int len = int(m.size());
  vector<vector<int> > ret(len, vector<int>(len));
  for (int i = 0; i < len; i++) ret[i][i] = 1;
  while (n) {
    if (n & 1) ret = mul(ret, m);
    n >>= 1;
    m = mul(m, m);
  }
  return ret;
}
void print(vector<vector<int> > m) {
  int p = int(m.size());
  int q = int(m[0].size());
  for (int(i) = 0, j123 = p; (i) < j123; (i)++)
    for (int(j) = 0, j123 = q; (j) < j123; (j)++)
      cout << m[i][j] << (j + 1 < q ? ' ' : '\n');
}
long long N;
int K;
int choose[100][100];
int main() {
  ios_base::sync_with_stdio(0);
  cout.precision(15);
  cout << fixed;
  cout.tie(0);
  cin.tie(0);
  cin >> N >> K;
  choose[0][0] = 1;
  for (int i = 1; i <= 88; i++) {
    choose[i][0] = choose[i][i] = 1;
    for (int j = 1; j < i; j++)
      choose[i][j] = add(choose[i - 1][j - 1], choose[i - 1][j]);
  }
  int len = (K + 1) * 2 + 1;
  vector<vector<int> > m(len, vector<int>(len));
  for (int kk = 0; kk <= K; kk++) {
    for (int j = 0; j <= kk; j++) {
      m[kk][j] = choose[kk][j];
    }
  }
  for (int kk = 0; kk <= K; kk++) {
    for (int j = 0; j <= kk; j++) {
      for (int l = 0; l <= j; l++) {
        int x = mul(choose[kk][j], choose[j][l]);
        m[kk][K + 1 + l] = add(m[kk][K + 1 + l], x);
      }
    }
  }
  for (int delta = 0; delta <= K; delta++) {
    m[K + 1 + delta][delta] = 1;
  }
  m[len - 1][K] = 1;
  m[len - 1][len - 1] = 1;
  vector<vector<int> > m2(len, vector<int>(1));
  for (int i = 0; i < len; i++) {
    if (i <= K) {
      int val = 1;
      for (int(jjjjj) = 0, j123 = i + 1; (jjjjj) < j123; (jjjjj)++)
        val = mul(val, 2);
      m2[i][0] = val;
    } else {
      m2[i][0] = 1;
    }
  }
  vector<vector<int> > ret = mypow(m, N - 1);
  vector<vector<int> > ret2 = mul(ret, m2);
  long long ans = ret2[len - 1][0];
  ans %= MOD;
  ans += MOD;
  ans %= MOD;
  cout << ans << '\n';
}