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 int mod = 1e9 + 7;
long long int N, K, komb[100][100];
inline long long int mul(long long int a, long long int b) {
  return (long long int)a * b % mod;
}
inline void f(long long int &a) {
  if (a >= mod) a -= mod;
}
long long int us(long long int a, long long int b) {
  long long int cur = a, k = 0, ret = 1;
  while (b) {
    if ((1 << k) & b) {
      ret = mul(ret, cur);
      b -= (1 << k);
    }
    cur = mul(cur, cur);
    k++;
  }
  return ret;
}
void cal() {
  komb[0][0] = 1;
  for (long long int i = 1; i <= K + 5; i++) {
    komb[i][0] = 1;
    for (long long int j = 1; j <= i; j++)
      komb[i][j] = komb[i - 1][j] + komb[i - 1][j - 1], f(komb[i][j]);
  }
}
class mat_mul {
 public:
  long long int tmp[100][100], cur[100][100], bg[100], sze;
  void fill() {
    K++;
    sze = 2 * K + 1;
    for (long long int i = 1; i <= K; i++) bg[2 * i - 1] = 1;
    for (long long int i = 1; i <= K; i++) bg[2 * i] = us(2, i);
    bg[sze] = 1;
    for (long long int i = 1; i < sze; i += 2) cur[i + 1][i] = 1;
    for (long long int i = 2; i < sze; i += 2) {
      for (long long int j = i; j >= 1; j -= 2)
        cur[j][i] = komb[i / 2 - 1][(i - j) / 2];
      for (long long int j = i - 1; j >= 1; j -= 2)
        cur[j][i] = mul(cur[j + 1][i], us(2, (i - 1 - j) / 2));
    }
    cur[sze][sze] = 1;
    cur[sze - 1][sze] = 1;
  }
  void next() {
    for (long long int i = 1; i <= sze; i++)
      for (long long int j = 1; j <= sze; j++) {
        tmp[i][j] = 0;
        for (long long int k = 1; k <= sze; k++)
          tmp[i][j] += mul(cur[i][k], cur[k][j]), f(tmp[i][j]);
      }
    for (long long int i = 1; i <= sze; i++)
      for (long long int j = 1; j <= sze; j++) cur[i][j] = tmp[i][j];
  }
  long long int last() {
    for (long long int i = 1; i <= sze; i++) {
      tmp[1][i] = 0;
      for (long long int j = 1; j <= sze; j++)
        tmp[1][i] += mul(bg[j], cur[j][i]), f(tmp[1][i]);
    }
    for (long long int i = 1; i <= sze; i++) bg[i] = tmp[1][i];
    return bg[sze];
  }
} asd;
int main() {
  scanf("%lld %lld", &N, &K);
  if (N == 1) {
    printf("1\n");
    return 0;
  }
  cal();
  N--;
  asd.fill();
  while (N) {
    if (N & 1) asd.last();
    asd.next();
    N >>= 1;
  }
  printf("%lld\n", asd.bg[asd.sze]);
  return 0;
}