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 mmod = 1000000007;
int fib(long long m) {
  int a[2][2] = {0};
  int i[2][2] = {0};
  a[0][0] = a[0][1] = a[1][0] = i[0][0] = i[1][1] = 1;
  int res[2][2] = {0};
  res[0][0] = res[1][1] = 1;
  for (int bit = 62; bit >= 0; bit--) {
    {
      int b[2][2] = {0};
      for (int p = 0; p < 2; p++)
        for (int q = 0; q < 2; q++)
          for (int r = 0; r < 2; r++)
            b[p][q] = (b[p][q] + 1LL * res[p][r] * res[r][q]) % mmod;
      for (int p = 0; p < 2; p++)
        for (int q = 0; q < 2; q++) res[p][q] = b[p][q];
    }
    if (m & (1LL << bit)) {
      int b[2][2] = {0};
      for (int p = 0; p < 2; p++)
        for (int q = 0; q < 2; q++)
          for (int r = 0; r < 2; r++)
            b[p][q] = (b[p][q] + 1LL * res[p][r] * a[r][q]) % mmod;
      for (int p = 0; p < 2; p++)
        for (int q = 0; q < 2; q++) res[p][q] = b[p][q];
    }
  }
  return res[0][0];
}
int pw(long long n, long long m) {
  n %= mmod;
  if (m == 0) return 1;
  int res = pw(n, m / 2);
  res = (1LL * res * res) % mmod;
  if (m % 2) res = (1LL * res * n) % mmod;
  return res;
}
int main() {
  int combi[41][41] = {0};
  combi[0][0] = 1;
  for (int i = 0; i < 40; i++)
    for (int j = 0; j < 40; j++) {
      combi[i + 1][j] = (combi[i + 1][j] + combi[i][j]) % mmod;
      combi[i + 1][j + 1] = (combi[i + 1][j + 1] + combi[i][j]) % mmod;
    }
  long long n;
  int m;
  cin >> n >> m;
  if (n <= 2) {
    int res = 0;
    for (int i = 1; i <= n; i++) res = (res + 1LL * fib(i) * pw(i, m)) % mmod;
    cout << res << endl;
    return 0;
  }
  int R[41];
  R[0] = (fib(n) * 2LL + fib(n - 1) - 2 + mmod) % mmod;
  R[0] = (R[0] + mmod) % mmod;
  for (int i = 1; i <= m; i++) {
    int right = (1 + pw(2, i + 1)) % mmod;
    right = (right - 1LL * fib(1) * pw(2, i)) % mmod;
    right = (right - 1LL * fib(n) * pw(n + 1, i)) % mmod;
    right = (right - 1LL * fib(n - 1) * pw(n + 1, i)) % mmod;
    right = (right - 1LL * fib(n) * pw(n + 2, i)) % mmod;
    for (int j = 1; j <= i; j++) {
      int partial = (1LL * combi[i][j] * R[i - j]) % mmod;
      right = (right + 1LL * partial * (1 + pw(2, j))) % mmod;
    }
    R[i] = (-right + mmod) % mmod;
  }
  cout << R[m] << endl;
}