#include <fstream>
using namespace std;

ifstream cin( "sandokan.in" );
ofstream cout( "sandokan.out" );

const int MOD = 2e6 + 3;

int v[ 5001 ];
int n, k;

int main()
{
    cin >> n >> k;
    n--;

    k = n % ( k - 1 );

    v[ 1 ] = 1;
    for( int i = 2; i <= n + 1; i++ ) {
        for( int j = i; j >= 1; j-- )
            v[ j ] = ( v[ j ] + v[ j - 1 ] ) % MOD;
    }

    cout << v[ k + 1 ] << '\n';
    return 0;
}