#include <fstream>

using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

int n,k,i,j,x,v[5005];

int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>x;
    n--;
    if(k-1==0){
        fout<<1;
        return 0;
    }
    k=n%(k-1);
    v[0]=v[1]=1;
    for(i=2;i<=n;i++){
        v[0]=1;

        for(j=i;j>=1;j--)
            v[j]=(v[j]+v[j-1])%2000003;
    }
    fout<<v[k];
    return 0;
}