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 mod = 1e9 + 7;
int p[70], q[70];
map<pair<long long, int>, int> m;
map<long long, int> M;
int c[65][65], pw[65] = {1};
int pow(long long a, int b) {
  if (b == 0) return 1;
  if (b & 1) return (int)((a % mod) * pow(a, b - 1) % mod);
  int c = pow(a, b / 2);
  return (int)(1ll * c * c % mod);
}
int fib(long long n) {
  if (n == -1) return 0;
  if (n <= 1) return 1;
  if (M.count(n)) return M[n];
  int ans;
  long long nn = n;
  int k = -1;
  while (nn) {
    nn >>= 1;
    k++;
  }
  ans = (int)((1ll * fib(n - (1ll << k)) * p[k] % mod +
               1ll * fib(n - 1 - (1ll << k)) * q[k] % mod) %
              mod);
  M[n] = ans;
  return ans;
}
void compute() {
  int i, j;
  for (i = 0; i <= 40; i++) c[i][0] = 1;
  for (i = 0; i <= 40; i++)
    for (j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
  for (i = 1; i <= 60; i++) pw[i] = 2 * pw[i - 1] % mod;
  p[0] = 1;
  q[0] = 1;
  for (i = 1; i <= 60; i++) {
    p[i] = (int)((1ll * p[i - 1] * p[i - 1] % mod +
                  1ll * q[i - 1] * q[i - 1] % mod + mod) %
                 mod);
    q[i] = (int)((1ll * 2 * p[i - 1] * q[i - 1] % mod -
                  1ll * q[i - 1] * q[i - 1] % mod + mod) %
                 mod);
  }
}
int A(long long n, int k) {
  pair<long long, int> pr;
  pr.first = n;
  pr.second = k;
  if (m.count(pr)) return m[pr];
  int ans;
  ans = pow(n + 2, k);
  ans = (int)((1ll * ans * fib(n + 2)) % mod);
  ans = ((ans - pw[k] - 1) % mod + mod) % mod;
  for (int j = 0; j <= k - 1; j++)
    ans = (ans - (int)(1ll * c[k][j] * A(n + 1, j) % mod) + mod) % mod;
  for (int j = 0; j <= k - 1; j++)
    ans =
        (ans - (int)((1ll * c[k][j] * pw[k - j]) % mod * A(n, j) % mod) + mod) %
        mod;
  m[pr] = ans;
  return ans;
}
int main() {
  int k;
  long long n;
  compute();
  scanf("%I64d %d", &n, &k);
  int ans = A(n, k);
  printf("%d", ans);
}