#include <fstream>
#include <cstring>
#define mod 2000003

using namespace std;

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

int N,K,P[5005],C[5005],X;
int main(){
    fin>>N>>K;
    X=N%(K-1);
    if(X==0)
        X=K-1;
    X--;
    C[0]=1;
    for(int i=1;i<=N-1;i++){
        memcpy(P,C,sizeof(C));
        for(int j=1;j<=X && j<=i;j++)
            C[j]=(P[j-1]+P[j])%mod;
    }
    fout<<C[X]<<"\n";
    fin.close();fout.close();
    return 0;
}