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.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author George Marcus
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    private static final int MOD = 1000000007;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        long N = in.nextLong();
        int K = in.nextInt();

        int[][] comb = new int[K + 1][K + 1];
        comb[0][0] = 1;
        for(int i = 1; i <= K; i++) {
            comb[i][0] = comb[i][i] = 1;
            for(int j = 1; j < i; j++) {
                comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
                if(comb[i][j] >= MOD)
                    comb[i][j] -= MOD;
            }
        }

        int[][] A = new int[2 * K + 3][2 * K + 3];
        for(int k = 0; k <= K; k++) {
            for(int i = 0; i <= k; i++)
                A[i][k] = comb[k][k - i];
            for(int i = K + 1; i <= K + 1 + k; i++)
                A[i][k] = (int) (comb[k][k - (i - (K + 1))] * (1L << (k - (i - (K + 1)))) % MOD);
        }
        for(int k = K + 1; k <= 2 * K + 1; k++)
            A[k - (K + 1)][k] = 1;
        for(int i = 0; i <= 2 * K + 1; i++)
            A[i][2 * K + 2] = A[i][K];
        A[2 * K + 2][2 * K + 2] = 1;

        int[][] R = fastPow(A, N - 1);

        long ans = 0;
        for(int i = 0; i <= K + 1; i++) {
            ans += R[i][2 * K + 2];
        }
        ans += R[2 * K + 2][2 * K + 2];
        ans %= MOD;

        out.println(ans);
    }

    private int[][] fastPow(int[][] A, long P) {
        int[][] R = new int[A.length][A.length];
        for(int i = 0; i < R.length; i++)
            R[i][i] = 1;

        while(P > 0) {
            if((P & 1) > 0)
                R = mult(R, A);
            A = mult(A, A);
            P >>= 1;
        }

        return R;
    }

    private int[][] mult(int[][] A, int[][] B) {
        int n = A.length;
        int[][] C = new int[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++) {
                long crt = 0;
                for(int k = 0; k < n; k++) {
                    crt += (long)A[i][k] * B[k][j];
                    if(crt > 1e16)
                        crt %= MOD;
                }
                crt %= MOD;
                C[i][j] = (int) crt;
            }
        return C;
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public long nextLong() {
        return Long.parseLong(nextString());
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));

        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    }