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



    return 0;
}