#include <fstream>
#define f in
#define g out
#define MOD  2000003

using namespace std;
ifstream in ( "sandokan.in" );
ofstream out( "sandokan.out" );
int n, k, i, j, t, x;
int d[2][5050];

int main() {
    f>>n>>k;
    x = n;
    while ( x >= k )
        x -= k-1;
    x--; n--;
    
    d[1][0] = 1;
    for ( i=1; i <= n; i++ ){
        d[t][0] = 1;
        for( j=1; j <= i; j++ )
            d[t][j] = ( d[1-t][j] + d[1-t][j-1] ) % MOD;
        t = 1-t;
    }
    
    g<<d[1-t][x];
    return 0;
}