#000073

z-stepenice

Mister S zeli da novoj drugarici Miss N prikaze lepe strane Novog Sada (kojih, jel' te, ima na pregrst)
i odlucio je da je odvede na Petrovaradinsku tvrdjavu. Svi dobro znaju da do mesta sa kojih se Novi Sad
lepo vidi sa tvrdjave vodi puno stepenica (Mister S tacno zna koliko do kog mesta). Shodno tome da se
Miss N bavi matematikom, njoj je u jednom trenutku u toku setnje "pao na pamet" sledeci problem:
- Ako mogu da peskocim najvise <B>k</B> stepenica u jednom trenutku, a znam koliko stepenica ima
do zeljenog cilja, na koliko razlicitih nacina mogu da dodjem do cilja?
<br><br>

Naravno, dva nacina su razlicita ako je niz stepenica kojim smo se popeli do cilja razlicit.
<br><br>

Posto Mister S zeli da se pokaze kako je dobar matematicar, zeli da resi problem pre Miss N. Shodno
tome da je Mister S previse okupiran Miss N, on ne moze da razmislja o tom problemu, pa je zatrazio pomoc
od malog Z, ali mali Z se sprema da ode na zurku sa drustvom, pa problem prepusta vama. Vi treba
da pomognete malom Z, a samim tim i Mister S, i kazete na koliko nacina se moze doci do zeljenog cilja, ako znamo
da do cilja ima <B>n</B> stepenica, a tokom svakog koraka se moze preskociti najvise <B>k</B> stepenica.
<br><br>

Ulaz:<br>
Sa standardnog ulaza se u prvom redu ucitavaju brojevi <B>n</B> (1 <= <B>n</B> <= 100000)
i <B>k</B> (1 <= <B>k</B> <= 100).
<br><br>

Izlaz:<br>
Na standardni izlaz ispisati resenje, na kolika nacina moze da se stigne do cilja, po modulu 1021987.
<br><br>

Primeri:<br><br>
Ulaz:<br>
3 2<br>
<br>
Izlaz:<br>
3<br>
<br>
Ako stepenice obelezimo brojevima od 1 do 3, onda je moguce kretati se na jedan
od sledecih nacina (1 , 2 , 3) , (1 , 3) , (2 , 3).
<br><br>
Ulaz:<br>
4 1<br>
<br>
Izlaz:<br>
1<br>
<br>
Postoji samo jedan nacin, a to je da se penje ne preskacuci stepenice.
<br><br>
Ulaz:
999 99<br>
<br>
Izlaz:<br>
<br>144494
<br>
Ima puno nacina :)

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.