#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;
int n,i,j,v[5005],k,d[5005][5005][3],creds,sol;
ifstream f("sandokan.in");
ofstream g("sandokan.out");


int main()
{
    f>>n>>k;
    for(i=1;i<=n;i++) f>>v[i];
    for(i=1;i<=n;i++)
    {
        d[i][i][0]=1;
        creds=i-k;
        while(creds>0)
        {
            d[i][creds][0]=(d[i-1][creds-1][1]+d[i-1][creds-1][0])%2000003;
            creds-=k;
        }
        if(i>=k)
        {
            d[i][i-k][1]=1;
            creds=i-2*k;
            while(creds>0)
            {
                d[i][creds][1]=(d[i-1][creds+k][0]+d[i-1][creds+k][1])%2000003;
                creds-=k;
            }
        }
    }
    for(i=0;i<k;i++)
    {
        sol+=d[n][i][0]+d[n][i][1];
        sol%=2000003;
    }
    g<<sol<<'\n';
    return 0;
}