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.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class yet_another
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static long mod=(long)(1e9+7);
	static int[][] c;
	static int maxn=(int)51;
	
	static int add(long a,long b)
	{
		long ret=a+b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int mul(long a,long b)
	{
		long ret=a*b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int pow(int a,long b)
	{
		int x=1,y=a;
		
		while(b>0)
		{	
			if(b%2==1)
			{
				x=mul(x,y);
			}
			
			y=mul(y,y);b=b/2;
		}
		
		return x;
	}
	
	static void build()
	{
		c=new int[maxn][maxn];c[0][0]=1;
		
		for(int i=1;i<maxn;i++)
		{
			c[i][0]=1;
			
			for(int j=1;j<=i;j++)
			{
				c[i][j]=add(c[i-1][j],c[i-1][j-1]);
			}
		}
	}
	
	static int[][] matrix_mul(int[][] a,int[][] b,int r1,int c1,int r2,int c2) throws Exception
	{
		if(c1!=r2)
		{
			throw new Exception("Matrices not fit for multiplication!");
		}
		
		int[][] c=new int[r1][c2];
		
		for(int i=0;i<r1;i++)
		{
			for(int j=0;j<c2;j++)
			{
				for(int k=0;k<c1;k++)
				{
					int now=mul(a[i][k],b[k][j]);
					
					c[i][j]=add(c[i][j],now);
				}
			}
		}
		
		return c;
	}
	
	static int[][] id(int n) throws Exception
	{
		int[][] ret=new int[n][n];
		
		for(int i=0;i<n;i++)
		{
			ret[i][i]=1;
		}
		
		return ret;
	}
	
	static int[][] matrix_pow(int[][] a,long b,int n) throws Exception
	{
		int[][] x=id(n),y=a;
		
		while(b>0)
		{
			if(b%2==1)
			{
				x=matrix_mul(x,y,n,n,n,n);
			}
			
			y=matrix_mul(y,y,n,n,n,n);b=b/2;
		}
		
		return x;
	}
	
    public static void main(String args[]) throws Exception
    {
		build();long n=sc.nextLong();int k=sc.nextInt(),size=((k+1)*2)+1;
		
		int[][] a=new int[size][size];
		
		for(int j=0;j<=k;j++)
		{
			for(int i=0,ctr=0;ctr<=j;i++,ctr++)
			{
				a[i][j]=c[j][ctr];
			}
			
			for(int i=k+1,ctr=0;ctr<=j;i++,ctr++)
			{
				a[i][j]=mul(c[j][ctr],pow(2,j-ctr));
			}
		}
		
		for(int j=k+1;j<=2*k+1;j++)
		{
			a[j-(k+1)][j]=1;
		}
		
		a[k][size-1]=1;a[size-1][size-1]=1;
		
		if(n==1 || n==2)
		{
			int[] f=new int[]{0,1,2};int res=0;
			
			for(int i=1;i<=n;i++)
			{
				int now=mul(f[i],pow(i,k));
				
				res=add(res,now);
			}
			
			out.println(res);
		}
		
		else
		{
			int[][] now=matrix_pow(a,n-2,size),val=new int[1][size];
			
			for(int i=0;i<=k;i++)
			{
				val[0][i]=mul(2,pow(2,i));
			}
			
			for(int i=k+1;i<=2*k+1;i++)
			{
				val[0][i]=1;
			}
			
			val[0][size-1]=1;
			
			now=matrix_mul(val,now,1,size,size,size);
			
		//	out.println(Arrays.deepToString(val)+" "+Arrays.deepToString(now));
			
			int res=add(now[0][k],now[0][size-1]);
			
			out.println(res);
		}
		
		out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}