#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 15
#define p 1000000007
#define int long long
using namespace std;
struct jz{
	int m[30][30];
	jz(){memset(m,0,sizeof(m));}
}a,b,cc; 
int n,m,l,k;
char c[1919810]; 
jz mul(jz a,jz b){
	jz res;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int kk=1;kk<=k;kk++){
				res.m[i][j]=(res.m[i][j]+a.m[i][kk]*b.m[kk][j]%p)%p;
			}
		}
	}
	return res;
}
int csh(int k){
	for(int i=1;i<=k;i++)a.m[1][i]=1;
	for(int i=1;i<=k;i++){
		b.m[2][i]=b.m[i][i]=1;
		for(int j=2;j<i;j++){
			b.m[j][i]=(b.m[j-1][i]+b.m[j-1][i-1])%p;
		}
	}
	
	b.m[k][k]=2;
	for(int i=2;i<=k;i++)b.m[i][1]=b.m[i][k];	
}
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=a*res%p;
		a=a*res%p;
		b>>=1;
	}
	return res;
}
int solve(int n){
	jz res=b;
	int kk=n;
	while(kk){
		if(kk&1)res=mul(res,b);
		b=mul(b,b);
		kk>>=1;
	}
	return mul(cc,res).m[1][1]%p+qpow(n%p,k-2)%p;
}
signed main(){
	scanf("%lld%lld",&n,&k);
	k+=2;
	csh(k);
	printf("%lld",solve(n)%p);
	return 0;
}