#include <fstream>
using namespace std;
int ant[5010], crt[5010];
int main(){
    ifstream fin("sandokan.in");
    ofstream fout("sandokan.out");
    int n, k;
    fin >> n >> k;
    int m = n;
    while (m >= k) {
        m -= (k - 1);
    }
    ant[0] = ant[1] = crt[0] = 1;
    for (int i = 2; i <= n - 1; i++) {
        for (int j = 1; j <= i; j++) {
            crt[j] = (ant[j] + ant[j - 1]) % 2000003;
        }
        for (int j = 1; j <= i; j++) {
            ant[j] = crt[j];
        }
    }
    fout << crt[m - 1];
    return 0;
}





/**
1. Permutari
Am n obiecte distincte. Cate posibilitati am sa le asez intr-un sir pe toate.
n = 3. Codificam obiecteke prin 1,2,3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Dar cu 4 obiecte ? {1,2,3,4}

4 1 2 3
1 4 2 3
1 2 4 3
1 2 3 4

4 1 3 2
1 4 3 2
1 3 4 2
1 3 2 4

Daca P[3] = numarul depermutari de ordin 3, cum din fiecare permutare de ordin 3
obtin 4 permutari de ordin 4,
avem P[4] = P[3] * 4

P[1] = 1;
P[2] = 2
P[3] = 6
P[4] = 24

Permutarile au un singur parametru n si numarul lor este n!


Am in clasa n elevi. Doresc sa aleg k pentru a ma ajuta cu caratul manualelor.
In cate moduri ii pot alege pe cei k din cei n ?
Am multimea {1,2,3,4,...,n} si un k, in cate moduri pot selecta din multime
k elemente (distincte)
n = 5 si k = 3
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Daca ordinea elementelor din cadrul multimii nu conteaza (de fapt noi algoritmic
generam doar solutii cu elemente in ordine crescatoare) solutiile se
numesc combinari

Numarul de moduri de a alege k elemente dintr-o multime cu n elemente
se numeste combinari de n luate cate k (cosideram ca daca permutam
elementele unei solutii NU obtinem o solutie noua, de aceea
cand se genereaza, pentru un set de valori se afiseaza doar solutia cu ele crescator)

Formula: C[n][k] = n! / (k! * (n-k)!)
fie sirul {1,2,3,4,5}
1 2 3 4 5
1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 1 0 0
0 1 0 1 0
0 1 0 0 1
0 0 1 1 0
0 0 1 0 1
0 0 0 1 1
Combinari de n luare cate k = cate submultimi cu k elemente are o multime cu n elemente
Mai sus avem C[5][2] = 10

C[5][0] = 1
1 2 3 4 5
0 0 0 0 0

C[5][1] = 5
1 2 3 4 5
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

C[5][3] = 10 (le iau pe cele C[5][2] si observ ca sunt aceleasi dar daca iau in calcul
zerourile, nu unurii)
1 2 3 4 5
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0

C[5][4] = 5
1 2 3 4 5
1 1 1 1 0
1 1 1 0 1
1 1 0 1 1
1 0 1 1 1
0 1 1 1 1

C[5][5] = 1
1 2 3 4 5
1 1 1 1 1

C[n][0] + C[n][1] + C[n][2] + ... C[n][n] = 2^n

C[5][0] + C[5][1] + C[5][2] + C[5][3] + C[5][4] +C[5][5] =
1 + 5 + 10 + 10 + 5 + 1 = 32
numarul de submultimi cu 0 elemente ale unei multimi cu 5 elemente +
numarul de submultimi cu 1 elemente ale unei multimi cu 5 elemente +
numarul de submultimi cu 2 elemente ale unei multimi cu 5 elemente +
numarul de submultimi cu 3 elemente ale unei multimi cu 5 elemente +
numarul de submultimi cu 4 elemente ale unei multimi cu 5 elemente +
numarul de submultimi cu 5 elemente ale unei multimi cu 5 elemente =
= numarul total de submultimi ale unei multimi cu 5 elemente 2^5


C[n][k] = C[n][n-k]

n!/(k!(n-k)!)   n/((n-k)!*k!)

C[17][14] = C[17][3]


3 Aranjamente de k alemente ale unei multimi cu n elemente insemna
numarul de "submultimi" de k elemente distincte ale multimii cu n elemnte
dar mai conteaza si in ce ordine sunt elementele amestecate in submultime

Deducem ca de la fiecare combinare de n luate cate k, daca permutam in toate modurile
elementele combinarii obtinem un aranjament nou

Daca pentru n=5 si k = 3 am solutia 1 4 5 si la combinari este unica,
la aranjamente mai este si 1 5 4, 4 1 5, 4 5 1, 5 1 4, 5 4 1.

Numarul de aranjamente este egal cu numarul de combinari * k! (la fiecare combinare
de k elemente am k! moduri de a o permuta si obtin un aranjament nou)

A[n][k] = C[n][k] * P[k]

A[n][k] = n!/(k! * (n-k)!) * k! = n! / (n-k)!


Cum calculam permutari de n.
De multe ori, pentru evitarea de calcule anevoioase cu numere mari
se cere rezultatul modulo ceva (fiid vorba de produse, se face repede overflow
chiar si la long long).

p[1] = 1;
for (i=2;i<=n;i++)
    p[i] = p[i-1] * i % MOD;

Operatiile modulo functioneaza daca tin pe parcurs doar resturile insa numai
la adunare si inmultire (chiar si la scadere, dar daca ajunge negativ rezultatul mai adunam o data MOD)

daca a este intre 0 si MOD-1, b este intre 0 si MOD-1
atunci a-b:
- fie este intre 0 si MOD-1, deci nu am nimic de facu
- fie este mai mic decat 0, dar nu cu mult si daca mai adaug MOD il duc intre 0 si MOD-1

Problema apare la impartire unde sunt necesare artificii speciale (calcului invers
modularului - asta tine de matematica de a 12-a si vom invata ulterior)

Apare deci problema la calculul combinarilor pentru ca trebuie impartiri.


C[10][4] = 10!/(  6! * 4!  ) = 6! * (7*8*9*10) / (6! * 4!)
= (7*8*9*10)/(1*2*3*4)
Am mai simplificat dar tot an nevoie de impartiri.

O solutie mai anevoios de implementat este sa consideram numerele prime
care apar in descompunerea in factori primi a fiecarei valori si intr-un vector de
frecventa maresc pentru exponentii facorilor primi de la numarator si scad pentru
cei ai factorilor primi de la numitor
(7*8*9*10)/(1*2*3*4)

Iau numerele prime pana la 10 si descompun in factori primi numaratorul
2 3 5 7
4 2 1 1
Ce e mai sus este pentru numarator.
Fac la fel pentru numitor si scad exponentii in vectorul de frecventa
2 3 5 7
3 1
Scad

2 3 5 7
1 1 1 1
Ramane doar sa parcurg si sa fac doar inmultiri (aici se nimeri sa fie fiecare
numar prim o singura data, dar nu neaparat).
Avand doar inmultiri pot face linistit modulo.

In practica rareori este necesara aceasta tehnica deoarece
- daca n e mic, exista un algoritm n patrat, simplu
- daca n e mare de regula se cere modulo si atunci invers modulare


FORMULA
C[n][k] = C[n-1][k-1] + C[n-1][k]
C[n][0] = 1
C[n][n] = 1

  0  1  2  3  4  5
0 1
1 1  1
2 1  2  1
3 1  3  3  1
4 1  4  6  4  1
5 1  5 10 10  5  1

Pe fiecare linie este simetrie pentru ca C[n][k] = C[n][n-k]
Acesta se numeste Triunghiul lui Pascal
si elementele din el sunt valori ale combinarilor, de i luate cate j
(a+b)^1    =  1 1
(a+b)^2    =  1 2 1
(a+b)^3    =  1 3 3 1
(a+b)^4    =  1 4 6 4 1

Linia n din triunghiul lui Pascal reprezinta coeficientii descompunerii
(a+b)^n
Altfel spus, (a+b)^n = C[n][0] * a^n * b^0 + C[n][1] * a^(n-1) * b^1 +
C[n][2] * a^(n-2) * b^2 + ... pana se inverseaza C[n][n] * a^0 * b*n


for (i = 0; i <= n; i++)
C[i][0] = C[i][i] = 1; /// 1 pe coloana 0 si pe diagonala principala
for (i = 1; i <= n; i++)
for (j = 1; j < i; j++)
    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
!putem face si modulo pentru ca am doar adunare
Impedimentul este ca totusi am n ^ 2
**/