#include<fstream>
#define DIM 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k,s,v[10000],i,j;
int main(){
    fin>>n>>k;
    s=n%(k-1);
    if(s==0){
        s=k-1;
    }
    s--;
    v[0]=1;
    for(i=1;i<n;i++){
        for(j=i;j>0;j--){
            v[j]=v[j]+v[j-1];
            v[j]%=DIM;
        }
    }
    fout<<v[s];
    return 0;
}