//Problema Sandokan - Rezolvare C++: 100p -> infoarena.ro
//Stud. Cristian CRIȘAN - AC, CTI-RO, ANUL I

#include <iostream>
#include <fstream>

#define SIZE 5005
#define Modulo(x) (x) % 2000003

using namespace std;

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

void solve(int n, int k)
{
    int i, j, v[SIZE];
    v[0] = v[1] = 1;
    -- n;
    k = n % (k - 1);//se elimina toate elementele mai putin unul(cel de valoare maxima - este irelevant care element)
    if(k > n)
        fout << "1\n";
    for(i = 2; i <= n; ++ i)
        for(j = i; j > 0; -- j)
	  v[j] = Modulo(v[j] + v[j - 1]);//aplicam modulo 2000003 conform enuntului problemei
    fout << v[k] << '\n';
}

int main()
{
    int n, k;
    fin >> n >> k; //valoarea celor n numere nu influenteaza rezultatul, deci nu are rost sa le citim
    solve(n, k);
    return 0;
}