#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k,pascu[2][5010],o,o2;
int main(){
    fin>>n>>k;
    pascu[0][0]=1;
    for(int i=1;i<n;i++){
        pascu[i%2][0]=1;
        o=i+1;
        o2=i%2;
        for(int j=1;j<o;j++)
            if(pascu[1-o2][j-1]+pascu[1-o2][j]>=2000003)
                pascu[o2][j]=(pascu[o2][j-1]+pascu[1-o2][j])-2000003;
            else
                pascu[o2][j]=(pascu[1-o2][j-1]+pascu[1-o2][j]);
    }
    fout<<pascu[(n-1)%2][(n-1)%(k-1)];



    return 0;
}