#include<bits/stdc++.h>
using namespace std;
const int N=105,mod=1e9+7;

struct mat{
	long long v[N][N];
	int n,m;
	inline mat(){memset(v,0,sizeof(v));}
	inline mat(int a,int b,int one=0){
		n=a;m=b;
		memset(v,0,sizeof(v));
		if(one)for(int i=1;i<=n;i++)v[i][i]=1;
	}
	inline mat operator*(const mat b)
	{
		mat c=mat(n,b.m);
		for(int i=1;i<=n;i++)
			for(int k=1;k<=m;k++)
				for(int j=1;j<=b.m;j++)
					c.v[i][j]=(c.v[i][j]+(v[i][k]*b.v[k][j]%mod))%mod;
		return c;
	}
	inline void help()
	{
		cout<<n<<" "<<m<<"\n";
		for(int i=1;i<=n;i++,cout<<"\n")
			for(int j=1;j<=m;j++)
				cout<<v[i][j]<<" ";
		return;
	}
};
inline mat pw(mat a,int b)
{
	mat c=mat(a.n,a.n,1);
	while(b)
	{
		if(b&1)c=c*a;
		a=a*a;
		b>>=1;
	}
	return c;
}
inline int C(int a,int b)
{
	return tgamma(a+1)/tgamma(b+1)/tgamma(a-b+1);
}
long long n;
int k;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	n--;
	mat ans{k+2,k+2},q{1,k+2};
	for(int i=1;i<=k+2;i++)q.v[1][i]=1;
	ans.v[1][1]=2;
	for(int i=2;i<=k+2;i++)ans.v[i][1]=C(k,i-2);
	for(int i=2;i<=k+1;i++)
		for(int j=i;j<=k+2;j++)
		{
			ans.v[j][i]=C(k-i+2,j-i);
		}
	ans.v[k+2][k+2]=1;
	cout<<((q*pw(ans,n)).v[1][1]-(q*pw(ans,n-1)).v[1][1]+mod)%mod;
	return 0;
}

求调