Cerința

O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial se afla treapta 1)

Date de intrare

Programul citește de la tastatură numerele n și k.

Date de ieșire

Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.

Restricții și precizări

• 1 < n ≤ 1.000.000;
• 1 ≤ k ≤ n - 1;
• deoarece numărul va fi prea mare sa va afișa modulo 9001;
• la început, persoana se află pe treapta 1.

Exemplul 1:

Intrare

2 2

Ieșire

1

Explicație

Există o soluție, aceea când sare direct pe treapta 2.

Exemplul 2:

Intrare

4 2

Ieșire

3

Explicație

Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4