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 mod = 1e9 + 7;
long long bsize;
long long modpow(long long base, long long exp) {
  long long res = 1;
  base %= mod;
  while (exp > 0) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}
struct mat {
  long long val[100][100];
  int row, col;
  mat() {
    for (int i = 0; i < bsize; i++)
      for (int j = 0; j < bsize; j++) val[i][j] = 0;
  }
};
mat operator*(const mat &a, const mat &b) {
  mat result;
  for (int i = 0; i < bsize; i++) {
    for (int j = 0; j < bsize; j++) {
      for (int k = 0; k < bsize; k++)
        if (a.val[i][k] && b.val[k][j])
          result.val[i][j] =
              (result.val[i][j] + (a.val[i][k] % mod) * (b.val[k][j] % mod)) %
              mod;
    }
  }
  return result;
}
mat modpow(mat base, long long exp) {
  mat res;
  for (int i = 0; i < bsize; i++) res.val[i][i] = 1;
  while (exp > 0) {
    if (exp & 1) res = res * base;
    base = base * base;
    exp >>= 1;
  }
  return res;
}
int main() {
  const long long MOD = 1e9 + 7;
  long long n, k;
  scanf("%I64d %I64d", &n, &k);
  bsize = 2 * k + 3;
  long long fact[k + 1], inv[k + 1];
  fact[0] = inv[0] = 1;
  for (int i = 1; i <= k; i++) {
    fact[i] = fact[i - 1] * i % MOD;
    inv[i] = inv[i - 1] * modpow(i, MOD - 2) % MOD;
  }
  mat base;
  for (int i = 0; i <= k; i++) base.val[i][k + i + 1] = 1;
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= i; j++) {
      base.val[k + i + 1][j] = base.val[k + i + 1][k + j + 1] =
          fact[i] * inv[j] % MOD * inv[i - j] % MOD;
      base.val[k + i + 1][j] = base.val[k + i + 1][j] * modpow(2, i - j) % MOD;
    }
  }
  for (int i = 0; i < bsize - 1; i++)
    base.val[bsize - 1][i] = base.val[bsize - 2][i];
  base.val[bsize - 1][bsize - 1] = 1;
  long long a[bsize];
  for (int i = 0; i <= k; i++) {
    a[i] = 0;
    a[k + i + 1] = 1;
  }
  a[0] = 1;
  a[k + k + 2] = 1;
  mat res = modpow(base, n - 1);
  long long ans = 0;
  for (int i = 0; i < bsize; i++)
    ans = (ans + res.val[bsize - 1][i] * a[i] % MOD) % MOD;
  printf("%I64d\n", ans);
  return 0;
}