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

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Scara

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 si vrea sa stie in cate moduri poate sa urce scara.
(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 a scarii si k reprezinta numarul maxim de pasi pe care poate mutantul sa faca deodata.

Date de ieșire

Numarul de moduri de a urca scara modulo 1999999973

Restricții

• n≤1000000
• k≤100

Exemplu

Explicație

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