#include <fstream>
#include <cstring>
#define mod 2000003
#define dim 5005
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,i,j,c1[dim],c2[dim],v[dim],nr,p,k;
int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++){
        fin>>v[i];
    }
    if(n%(k-1)==0){
        p=k-1;
    }
    else{
        p=n%(k-1);
    }
    c1[0]=1;
    for(i=1;i<=n-1;i++){
        for(j=i;j>=1;j--){
            c2[j]=(c1[j]+c1[j-1])%mod;
        }
        memcpy(c1,c2,sizeof(c2));
    }
    fout<<c2[p]<<"\n";

    return 0;
}