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



    return 0;
}