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;
void rwFile() {
  freopen(
      "task"
      ".in",
      "r", stdin);
  freopen(
      "task"
      ".out",
      "w", stdout);
}
const long long MOD = 1e9 + 7;
long long n, k;
vector<long long> Pascal[45];
void calculatePascal() {
  Pascal[0] = {1};
  Pascal[1] = {1, 1};
  for (int i = 2; i < 45; i++) {
    Pascal[i].push_back(1);
    for (int j = 1; j < i; j++) {
      Pascal[i].push_back((Pascal[i - 1][j - 1] + Pascal[i - 1][j]) % MOD);
    }
    Pascal[i].push_back(1);
  }
}
struct Matrix {
  long long c[2][2];
  Matrix(int a) {
    c[0][1] = c[0][0] = c[1][0] = 1;
    c[1][1] = 0;
  }
  Matrix() {
    c[0][0] = c[1][1] = 1;
    c[0][1] = c[1][0] = 0;
  }
};
Matrix mult(Matrix a, Matrix b) {
  Matrix x = Matrix();
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      x.c[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        x.c[i][j] += a.c[i][k] * b.c[k][j];
        x.c[i][j] %= MOD;
      }
    }
  }
  return x;
}
Matrix Exp(Matrix a, long long e) {
  if (e == 0) {
    Matrix res = Matrix();
    return res;
  }
  Matrix x = Exp(a, e / 2);
  if (e % 2 == 0) {
    return mult(x, x);
  }
  return mult(mult(x, x), a);
}
long long Fibonacci(long long n) {
  Matrix x = Matrix(1);
  Matrix res = Exp(x, n + 1);
  return res.c[0][1];
}
long long Pow(long long b, int e = MOD - 2) {
  while (b < 0) b += MOD;
  b %= MOD;
  if (e == 0) return 1LL;
  long long x = Pow(b, e / 2);
  if (e % 2 == 0) {
    long long res = x * x % MOD;
    return res;
  }
  long long res = (x * x) % MOD * b % MOD;
  return res;
}
long long coefficient(long long t, long long tt) {
  long long tmp = 0;
  for (int i = 0; i <= t; i++) {
    long long x = Pow(tt - t + i, k) * Pascal[t][i] % MOD;
    if (i % 2 == 0)
      tmp = (tmp + x) % MOD;
    else
      tmp = (tmp - x + MOD) % MOD;
  }
  return tmp;
}
long long Result(long long x) {
  long long res = 0;
  for (int i = 0; i <= k; i++) {
    res += Fibonacci(x + 2 + i) * coefficient(i, x) % MOD;
    res %= MOD;
  }
  return res;
}
void solveC_YetAnotherNumberSequence() {
  calculatePascal();
  cin >> n >> k;
  long long res = Result(n) - Result(1) + 1 + MOD;
  cout << res % MOD;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solveC_YetAnotherNumberSequence();
  long long res = 0;
}