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 long long mod = 1e9 + 7;
long long n, k, x;
long long c[105][105];
long long f[105];
struct Mat {
  long long a[105][105];
  Mat() { memset(a, 0, sizeof(a)); }
  void init() {
    a[0][0] = 1;
    for (long long i = 1; i <= k + 1; i++)
      a[0][i + k + 1] = a[0][i] = c[k][i - 1];
    for (long long i = 1; i <= k + 1; i++)
      for (long long j = i; j <= k + 1; j++) {
        a[i][j] = a[i][j + k + 1] = c[k - i + 1][j - i];
        a[i + k + 1][j] = c[k - i + 1][j - i];
      }
  }
} m;
Mat operator*(Mat a, Mat b) {
  Mat c;
  c.init();
  for (long long i = 0; i < x; i++)
    for (long long j = 0; j < x; j++) {
      c.a[i][j] = 0;
      for (long long k = 0; k < x; k++) {
        c.a[i][j] += a.a[i][k] * b.a[k][j];
        c.a[i][j] %= mod;
      }
    }
  return c;
}
Mat operator^(Mat p, long long k) {
  Mat ans;
  ans = p;
  k--;
  while (k) {
    if (k & 1) ans = ans * p;
    k /= 2;
    p = p * p;
  }
  return ans;
}
void pre() {
  c[0][0] = c[1][0] = 1;
  for (long long i = 1; i <= 100; i++)
    for (long long j = 0; j <= i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  f[1] = 1;
  f[2] = 2;
  for (long long i = 3; i <= 100; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;
  }
}
long long pow_mod(long long a, long long n) {
  long long res = 1, t = a;
  while (n) {
    if (n & 1) res = (res * t) % mod;
    t = (t * t) % mod;
    n /= 2;
  }
  return res;
}
int main() {
  pre();
  cin >> n >> k;
  x = 3 + k * 2;
  Mat a;
  long long ans1 = 1, ans2 = 2 * pow_mod(2, k) % mod;
  if (n == 1)
    cout << ans1 << endl;
  else if (n == 2)
    cout << (ans1 + ans2) % mod << endl;
  else {
    a.a[0][0] = (ans1 + ans2) % mod;
    for (long long i = 1; i <= k + 1; i++) {
      a.a[i][0] = f[2] * pow_mod(2, k - i + 1);
      a.a[i + k + 1][0] = f[1] * pow_mod(2, k - i + 1);
    }
    Mat b;
    b.init();
    a = (b ^ (n - 2)) * a;
    cout << a.a[0][0] << endl;
  }
  return 0;
}