Wonderpot

#include <iostream>
using namespace std;
long long int dp[100010];
int main(){
    int n;
    cin >> n;
    int k;
    cin >> k;
    long long int coin[n+1];
    for(int i=0;i<=n;++i){
        if(i==0){
            dp[i]=1;
            coin[i]=dp[i];
        }
        else{
            if(i-k>0){
                dp[i]=dp[i]+coin[i-1]-coin[i-k-1];
            }

            else{
                dp[i]=dp[i]+coin[i-1];
            }
            if(dp[i]<0){
                dp[i]+=2009;
            }
            dp[i]=dp[i]%2009;
            coin[i]=dp[i]+coin[i-1];
            coin[i]=coin[i]%2009;
        }

    }
    cout << dp[n];

    return 0;
}