== include(page="template/taskheader" task_id="melodii") ==

Gigel a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Principala lui problema este ca nu cunoaste decat $2$ melodii (prima dureaza $1$ minut, iar a doua $2$ minute), dar el a fost chemat pentru exact $N$ minute de reprezentatii.

Gigel a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Principala lui problema este ca nu cunoaste decat 2 melodii. Prima melodie dureaza fix 1 minut, iar a doua fix 2 minute, dar el a fost chemat pentru exact N minute de reprezentatii.

Deoarece Gigel este student la FMI si nu la Conservator nu il deranjeaza acest lucru, in plus este curios sa stie pentru un N dat care este numarul de moduri de a dispune cele 2 melodii astfel incat reprezentatia sa dureze exact N minute. De exemplu pentru $N$ = 3, el are 3 posibilitati de dispunere a melodiilor : {1, 2} , {2, 1}, {1, 1, 1}.

Deoarece Gigel este student la FMI si nu la Conservator nu il deranjeaza acest lucru, in plus vrea sa stie pentru un N dat care este numarul de moduri de a dispune cele 2 melodii astfel incat sa dureze fix N minute. Mai exact pentru $N$ = 3, el are 3 posibilitati de dispunere a melodiilor : {1, 2} , {2, 1}, {1, 1, 1}.

Dupa ce a calculat pentru N <= 100 (cu backtracking) si-a dat seama ca acest numar este destul de mare, asa ca doreste sa afle doar restul impartirii acestui numar la R, numarul lui norocos. In plus el doreste raspunsul la aceasta intrebare pentru T valori diferite ale lui N.