Fişierul intrare/ieşire:scara.in, scara.outSursăad-hoc
AutorDin FolclorAdăugată dexiofurryNeagu Rares xiofurry
Timp execuţie pe test1 secLimită de memorie512 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile 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.inscara.out
3 2
3

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici