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.io.*;
import java.lang.reflect.Array;
import java.math.*;
import java.text.DecimalFormat;
import java.util.*;




public class Main {
    public static final int mod = 1000000007;
    private static int [] [] C;
    public static int add(int a,int b) {
        a += b;
        if (a >= mod) a -= mod;
        return a;
    }
    public static int mul(int a,int b){
        return (int)((a*(long)b)%mod);
    }

    private static void init(){
        int MAXK = 40;
        C = new int[MAXK+1][MAXK+1];
        for (int n = 0;n <= MAXK;n++){
            C[n][0] = C[n][n] = 1;
            for (int k = 1;k < n;k++)
                C[n][k] = add(C[n-1][k],C[n-1][k-1]);
        }
    }


    private static matrix buildMatrix(int K){
        matrix ret = new matrix(2*K+3);
        for (int i = 0;i <= K;i++) {
            int r = i+1,k = K - i;
            for (int j = 0;j <= k;j++) {
                int c = r + j;
                ret.A[r][c] = C[k][j];
            }
            for (int j = 0;j <= k;j++) {
                int c = r + j + K + 1;
                ret.A[r][c] = C[k][j];
            }
            for (int j = 1;j <= K+1;j++) {
                int rd = r + K+1;
                ret.A[rd][j] = ret.A[r][j];
            }

        }
        for (int i = 1;i < ret.n;i++)
            ret.A[0][i] = ret.A[1][i];
        ret.A[0][0] = 1;
        return ret;
    }

    private static int powmod(int x,int p) {
        if (p == 0) return 1;
        int y = 1;
        for (;p > 1;p >>= 1) {
            if (p%2 == 1) y = mul(x,y);
            x = mul(x,x);
        }
        return mul(x,y);
    }
    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        init();
        long n = io.getNextLong();
        int K = io.getNextInt();
        int S2 = add(1,powmod(2,K+1));
        if (n == 1)io.println(1);
        else {
            matrix mat = buildMatrix(K);
//            for (int i = 0;i < mat.n;i++)
//                System.err.println(Arrays.toString(mat.A[i]));
//            System.err.println("");
            int [] [] A = mat.exp(n-2);
            int [] B = new int[mat.n];
            B[0] = S2;
            for (int i = 0;i <= K;i++)
                B[i+1] = powmod(2,K-i + 1);
            for (int i = 0;i <= K;i++)
                B[i+K+2] = powmod(2,K-i);
//            for (int i = 0;i < mat.n;i++)
//                System.err.println(Arrays.toString(A[i]));
//            System.err.println("");
//            System.err.println(Arrays.toString(B));


            int [] C = new int[A.length];
            for (int i = 0;i < A.length;i++)
                for (int j = 0;j < A.length;j++)
                    C[i] = add(C[i],mul(A[i][j],B[j]));
//            System.err.println(Arrays.toString(C));
            io.println(C[0]);
        }
        io.close();
    }
}

class matrix{
    int [] [] A;
    int n;
    public matrix(int dim){
        A = new int[dim][dim];
        n = dim;
    }
    public void makeEye(){
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                A[i][j] = (i == j) ? 1 : 0;
    }
    public matrix mul(matrix O) {
        matrix C = new matrix(n);
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                for (int k = 0;k < n;k++)
                    C.A[i][j] = Main.add(C.A[i][j],Main.mul(A[i][k],O.A[k][j]));
        return C;
    }
    public int [] [] exp(long p) {
        matrix B = new matrix(n);
        matrix C = new matrix(n);
        C.makeEye();
        for (int i = 0;i < n;i++)
            for (int j = 0;j < n;j++)
                B.A[i][j] = A[i][j];

        if (p == 0) {
            B.makeEye();
            return B.A;
        }
        for (;p > 1;p >>= 1) {
            if (p%2 == 1) C = C.mul(B);
            B = B.mul(B);
        }
        return B.mul(C).A;
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}