#include <fstream>

using namespace std;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

typedef long long i64;

const int mod= 2000003;
const int nmax= 5000;

i64 d[2][nmax+1];

int main(  ) {
    i64 n, k;
    fin>>n>>k;
    k= (n-1)%(k-1);
    if ( n-k<k ) {
        k= n-k;
    }

    d[1][1]= d[1][0]= d[0][0]= 1;
    for ( i64 i= 2; i<=n; ++i ) {
        i64 a= i%2, b= (i+1)%2;
        for ( i64 j= 1; j<=k; ++j ) {
            d[a][j]= (d[b][j-1]+d[b][j])%mod;
        }
    }

    i64 sol= 1;
    if ( k>0 ) {
        sol= d[(n-1)%2][k];
    }
    fout<<sol<<"\n";

    return 0;
}