#include<cstdio>
#define RTT 2000003
#define NRMAX 5005
FILE *f=fopen("sandokan.in","r"), *g=fopen("sandokan.out","w");

int N, K, r, NrPrime;
int viz[NRMAX], Ciur[700], Fact[700];

void CreareCiur(){
int i, j;

    NrPrime = 0;
    for( i = 2; i <= N-1; i++ )
        if( viz[i] == 0 )
        {
            Ciur[ ++NrPrime ] = i;

            for( j = i*2; j <= N-1; j += i )
                viz[j] = 1;
        }
}

void Adauga( long int A, long int Semn ){
int a, i;

    for( i = 1; i <= NrPrime && Ciur[i] <= A; i++ )
    {
        a = Ciur[i];
        while( a <= A )
        {
            Fact[i] += Semn * ( A / a );
            a *= Ciur[i];
        }
    }

}

int Combinari( int n, int k ){
int i, j, R;

    Adauga( n, +1 );
    Adauga( k, -1 );
    Adauga( n-k, -1 );

    R = 1;
    for( i = 1; Ciur[i] <= n && i <= NrPrime; i++ )
        for( j = 1; j <= Fact[i]; j++ )
        {
            R = ( R * Ciur[i] ) % RTT;
            printf("%d %d\n",Ciur[i],j);
        }

    return R;
}

int main(){

    fscanf(f,"%d %d\n",&N,&K);

    r = N % (K-1);
    if( r == 0 )
        r = K-1;

    CreareCiur();

    fprintf(g,"%d\n", Combinari( N-1, r-1 ) );

return 0;
}