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 JAVA):

Solution:
import java.util.Arrays;
import java.util.Scanner;

public class C {
    static int MOD = 1000000007;
    static long MODSQR = MOD * 1L * MOD;

    public static int[][] mul(int[][] a, int[][] b) {
        int[][] result = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                long res = 0;
                for (int k = 0; k < a[0].length; k++) {
                    res = (res + a[i][k] * 1L * b[k][j]);
                    if (res > MODSQR)
                        res %= MOD;
                }
                result[i][j] = (int) (res % MOD);
            }
        }
        return result;
    }

    public static int[][] matpow(int[][] base, long exp) {
        int[][] result = new int[base.length][base.length];
        for (int i = 0; i < base.length; i++)
            result[i][i] = 1;
        while (exp > 0) {
            if ((exp & 1) != 0)
                result = mul(result, base);
            base = mul(base, base);
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        int k = in.nextInt();
        int[][] C = new int[k + 1][k + 1];
        C[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= k; j++)
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
        int[][] matrix = new int[2 * k + 3][2 * k + 3];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= i; j++) {
                matrix[i][j] = C[i][j];
                matrix[i][k + j + 1] = C[i][j];
            }
        }
        for (int i = k + 1; i <= 2 * k + 1; i++) {
            int left = i - k - 1;
            for (int j = 0; j <= left; j++) {
                matrix[i][j] = C[left][j];
            }
        }
        matrix[2 * k + 2][2 * k + 2] = 1;
        matrix[2 * k + 2][k] = 1;
        // for (long[] a : matrix)
        // System.out.println(Arrays.toString(a));
        int[][] columnMatrix = new int[2 * k + 3][1];
        for (int i = 0; i < 2 * k + 2; i++)
            columnMatrix[i][0] = 1;
        matrix = matpow(matrix, n);

        columnMatrix = mul(matrix, columnMatrix);
        // for (long[] a : columnMatrix)
        // System.out.println(Arrays.toString(a));
        System.out.println(columnMatrix[2 * k + 2][0]);
    }
}