# include <algorithm>
using namespace std ;

const char FIN[] = "sandokan.in", FOU[] = "sandokan.out";
const int MAX = 5005, MOD = 2000003;

int C[2][MAX] ;
int N, K, P ;

int main ()
{
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    scanf ( "%d %d", &N, &K ) ; --K ;

    P = N % K ? N % K - 1 : K - 1 ; --N ;

    C[0][0] = C[1][0] = 1;
    for ( int i = 1, k = 0; i <= N; ++i, k = !k ) {
        for ( int j = 1; j <= min ( i, P ); ++j ) {
            C[!k][j] = ( C[k][j - 1] + C[k][j] ) % MOD ;
        }
    }

    printf ( "%d", C[N & 1][P] ) ;

    return 0;
}