#include <fstream>
#define DIM 5011
#define MOD 2000003
using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
int n,k,poz;
int C[DIM];

int main(void){
    register int i,j;

    f>>n>>k;
    poz=n%(k-1);
    if(poz==0)
        poz=k-1;
    poz--;
    for(i=1;i<n;i++){
        C[0]=1;
        for(j=i;j>0;j--)
            C[j]=(C[j]+C[j-1])%MOD;
    }
    g<<C[poz];
    f.close();
    g.close();
    return 0;
}