Afişează mesaje
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
ma chinui de 3 ore sa gasesc o relatie de recurenta
