#define MD 10007
ll@k,@s,@n;
Mint a[n+k]{};
a[k]=s;
rep(i,1,n){
	Mint u=1,v=1;
	rep(j,k+1){
		a[k+i]+=a[k+i-j-1]/u;
		(u,v)=(v,u+v);
	}
}
wt(a[k+n-1]);