Trepte2.2

#include <iostream>
#define M 9001
using namespace std;
short dp[1000001];

int main()
{
    int n,k,MIN;
	cin>> n>>k;
	dp[1]=1;
	for(int i=2;i<n;++i)
    {
        MIN=min(k,i-1);
        dp[i]=(2*dp[i-1]-dp[i-MIN-1])%M;
        while(dp[i]>M)
            dp[i]-=M;
        if(dp[i]<0)
            dp[i]+=M;
    }
    MIN=min(k,n-1);
    dp[n]=dp[n-1]-dp[n-MIN-1];
    if(dp[n]<0)
        dp[n]+=M;
	cout<<dp[n];
	return 0;
}