#include<fstream>
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int i,j,n,k,n2,x,val,v1[5010],v2[5010];
int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>x;
    n2=(n-1)%(k-1)+1;
    v1[0]=1;
    v2[0]=1;
    v2[1]=1;
    val=3;
    while(val<=n-1){
        for(i=1;i<=val;i++){
            v1[i]=(v2[i]+v2[i-1])%2000003;
        }
        for(i=1;i<=val;i++)
            v2[i]=v1[i];
        val++;
    }
    fout<<v2[n2];





    return 0;
}