Pot old

#include<stdio.h>
typedef long long int ll;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    if(m == 1){
        printf("1");
        return 0;
    }
    ll table[n+1];
    table[0] = 1;
    table[1] = 1;
    ll sum = 2;
    int index = 0;
    for(int i=2;i<=n;i++){
        table[i] = sum%2009;
        sum += table[i];
        if(i-index == m){sum -= table[index];
            index++;
        }
    }
    printf("%lld",table[n]);
    return 0;
}