#include <fstream>
#define DIM 5005
#define MOD 2000003

using namespace std;

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

int n, k, i, j;
int c[2][DIM];

int main(){
    fin >> n >> k;
    /// elementul maxim va fi tot timpul in sirul final, deci practic daca in final am p elemente, unul e cel maxim, iar restul nu conteaza => combinari (n-1, p-1)
    /// numerele citite sunt irelevante
    /// doar ultimele 2 linii conteaza
    c[0][0] = 1;
    for (i=1; i<n; i++){
        c[i%2][0] = 1;
        for (j=1; j<=i; j++){
            c[i%2][j] = c[1-i%2][j] + c[1-i%2][j-1]%MOD;
        }
    }
    k = (n-1)%(k-1);
    fout << c[(n-1)%2][k];
    return 0;
}