#include <fstream>
using namespace std;
ifstream fin ("sandokan.in");
ofstream fout ("sandokan.out");
int pas[2][5050],i,k,n,ln,j;
void pascal(){
    pas[0][0]=1;
    //semn=1;
    for(i=1;i<n;i++){
        ln=1;
        pas[ln][0]=1;
        for(j=2;j<=i;j++){
            pas[ln][j]=pas[!ln][j]+pas[!ln][j-1];
            pas[ln][j]%=2000003;
        }
        ln = !ln;
    }
}
int main(){
    fin>>n>>k;
    k=(n-1)%(k-1);
    pascal();
    fout<<pas[(n-1)%2][k];

    return 0;
}