Pot mod qs

#include<stdio.h>
#define mod 2009
typedef long long int ll;
int main()
{
    ll n,k;
    scanf("%lld %lld",&n,&k);

    ll dp[n+1]; dp[0] = 1; dp[1] = 1;
    ll qs[n+1]; qs[0] = 1; qs[1] = 2;
    for(ll i = 2 ; i <= n ; i ++){
        ll st;//;
        if(i - k - 1 < 0)st = 0;
        else st = qs[i - k - 1];
        dp[i] = (qs[i-1] - st + mod) % mod;
        qs[i] = (qs[i-1] + dp[i] + mod) % mod;
    }
    printf("%lld",dp[n] % mod);
    return 0;
}