Fișierul intrare/ieșire: scara.in, scara.out Sursă ad-hoc
Autor din folclor Adăugată de xiofurryNeagu Rares xiofurry
Timp execuție pe test 1 sec Limită de memorie 512 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile trimise | Statistici

Scara

Notă importantă: această problemă a fost modificată față de original, în data de 25.10.2013, deoarece testul 10 avea n 10 000 000 iar restricția originală era n ≤ 1 000 000. Am relaxat restricția la n ≤ 1 000 000

Copilul Andrei vrea sa stie in cate moduri poate sa urce scara. Fiind mutant, el poate sa urce o treapta, doua, pana la k trepte deodata.
(Din pacate nu vrea sa se foloseasca de celalte super-puteri)

Date de intrare

Se da n si k, unde n reprezinta numarul de trepte ale scarii si k reprezinta numarul maxim de trepte pe care le poate urca mutantul la un pas.

Date de ieșire

Numarul de moduri de a urca scara modulo 1999999973

Restricții

  • n ≤ 10 000 000
  • k ≤ 100

Exemplu

scara.in scara.out
3 2
3

Explicație

Cele 3 moduri de a urca scara sunt:
1 1 1
1 2
2 1

Trebuie să te autentifici pentru a trimite soluții. Click aici