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 maxn = 83;
const long long maxs = 83;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 500;
long long ent[maxs][maxs];
long long zarib[maxs][maxs];
long long zarib2[maxs][maxs];
struct matris {
  long long u[maxs][maxs];
  matris() {
    for (char i = 0; i < maxn; i++) {
      for (char j = 0; j < maxn; j++) {
        u[i][j] = 0;
      }
    }
  }
};
matris operator*(const matris& a, const matris& b) {
  matris ans;
  for (char i = 0; i < maxn; i++) {
    for (char j = 0; j < maxn; j++) {
      ans.u[i][j] = 0;
    }
  }
  for (char i = 0; i < maxn; i++) {
    for (char j = 0; j < maxn; j++) {
      for (char k = 0; k < maxn; k++) {
        ans.u[i][k] += (a.u[i][j] * b.u[maxn - 1 - j][k]) % mod;
      }
    }
  }
  for (char i = 0; i < maxn; i++) {
    for (char j = 0; j < maxn; j++) {
      ans.u[i][j] %= mod;
    }
  }
  return ans;
}
matris operator^(matris a, long long b) {
  matris ans = matris();
  for (char j = 0; j < maxn; j++) {
    ans.u[j][j] = 1;
  }
  while (b > 0) {
    if (b & 1) {
      ans = ans * a;
    }
    b = (b >> 1);
    a = a * a;
  }
  return ans;
}
void pri(const matris& a) {
  cout << "===========\n";
  for (long long i = 0; i < maxn; i++) {
    for (long long j = 0; j < maxn; j++) {
      cout << a.u[i][j] << ' ';
    }
    cout << endl;
  }
  cout << "==============\n";
}
long long poww1(long long a) {
  if (a & 1) {
    return -1;
  }
  return 1;
}
long long poww2(long long b) {
  long long ans = 1;
  for (long long i = 0; i < b; i++) {
    ans *= 2;
    ans %= mod;
  }
  return ans;
}
int main() {
  ent[0][0] = 1;
  for (long long i = 1; i < maxs; i++) {
    ent[i][i] = 1;
    ent[i][0] = 1;
    for (long long j = 1; j < i; j++) {
      ent[i][j] = (ent[i - 1][j - 1] + ent[i - 1][j]) % mod;
    }
  }
  matris a = matris();
  long long n, k;
  cin >> n >> k;
  if (n == 1) {
    cout << 1;
    return 0;
  }
  maxn = 2 * k + 3;
  zarib[0][0] = 1;
  zarib2[0][0] = 1;
  for (long long i = 1; i < maxs; i++) {
    zarib[i][i] = 1;
    for (long long y = 0; y < i; y++) {
      for (long long z = 0; z <= y; z++) {
        zarib[i][z] =
            (zarib[i][z] + zarib[y][z] * ent[i][y] * poww1(i - y + 1)) % mod;
      }
    }
    for (long long y = 0; y <= i; y++) {
      for (long long z = 0; z <= y; z++) {
        zarib2[i][z] = (zarib2[i][z] + zarib[y][z] * zarib[i][y]) % mod;
      }
    }
  }
  a.u[2 * k + 2][0] = 1;
  a.u[2 * k + 2][k + 2] = 1;
  for (long long i = 0; i < k + 1; i++) {
    a.u[k + 1 + i][2 * k + 2 - i] = 1;
  }
  for (long long i = 0; i < k + 1; i++) {
    for (long long j = 0; j < k + 1; j++) {
      a.u[i][j + 1] = zarib2[i][k - j];
      a.u[i][j + k + 2] = zarib[i][k - j];
    }
  }
  matris b = matris();
  for (long long i = 0; i < k + 1; i++) {
    b.u[i][0] = (2 * poww2(i)) % mod;
  }
  for (long long i = k + 1; i < maxn - 1; i++) {
    b.u[i][0] = 1;
  }
  b.u[2 * k + 2][0] = 1;
  matris c;
  c = ((a ^ (n - 1)) * b);
  cout << c.u[0][0];
}