#include <fstream>
#define MOD 2000003
using namespace std;
ifstream fin ("sandokan.in");
ofstream fout ("sandokan.out");

int n, k, x;
int curent[5004], ant[5004];
int main()
{
    fin>>n>>k;
    for(int i=1; i<=n; i++)
        fin>>x;
    ///pot observa ca pt a calcula triunghiul lui pascal am nevoie doar de linia anterioara
    ///atunci o sa lucrez doar cu doi vectori
    ///ant[]-->care tine minte linia din matrice anterioara celei pe care o calculez
    ///curent[]-->linia curenta din matrice pe care o calculez
    ///daca ar fi cu matrice raspunsul ar fi c[n-1][p], deci eu trebuie sa calculez integral si linia n-1=> merg cu i=1, n-1

    ant[0]=ant[1]=1;///linia 1 din matrice
    for(int i=2; i<=n-1; i++)
    {
        curent[0]=1;///intotdeauna c[i][0]=1;
        for(int j=1; j<=i; j++)
            curent[j]=(ant[j]+ant[j-1])%MOD;
        ///pentru urm i, linia curenta devine anterioara, deci copiam pe curent in ant
        for(int j=0; j<=i; j++)
            ant[j]=curent[j];

    }
    fout<<curent[(n-1)%(k-1)];




    return 0;
}