#include <stdio.h>

#define MOD 2000003
#define aduna(x, y) (((x += y) >= MOD) ? (x -= MOD) : (0))

int N, K, P, v[5005], Comb[2][5005];

int main(void)
{
        int i, j, crt = 0, prev = 1;
        
        freopen("sandokan.in", "r", stdin);
        freopen("sandokan.out", "w", stdout);

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

        P = N % (K-1);
        if (!P) P = K-1;

        Comb[0][0] = 1;
        for (i = 1; i < N; ++i)
        {
                crt = (i & 1); prev = !crt;
                for (j = 0; j <= i; ++j)
                {
                        (!j) ? (Comb[crt][0] = 0) : (Comb[crt][j] = Comb[prev][j-1]);
                        aduna(Comb[crt][j], Comb[prev][j]);
                }
        }
        printf("%d\n", Comb[crt][P-1]);

        return 0;
}