Rezolvare PBinfo #1991

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 este pe 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 ≤ 100.000
• 1 ≤ k ≤ n - 1
• deoarece numărul va fi prea mare sa va afișa modulo 9001.

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