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

Lautarul Ghita a fost invitat la marea nunta a parlametarilor din Ferentari. Principala lui problema este ca nu stie decat 2 melodii. Prima melodie dureaza fix 1 minut, iar a doua fix 2 minute, dar el a fost angajat 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.

Lautarul Ghita stie sa calculeze dolarii pe frunte pe care ii va primi daca i se da secventa de melodii pe care le va interpreta, dar nu stie sa calculeze mai repede care este valoarea maxima pe care o poate primi, fapt pentru care va roaga pe voi sa ii spuneti pentru un numar N de minute cate secvente posibile de melodii exista. Ca de exemplu pentru un N = 3 el are 3 moduri diferite de a dispune melodiile : {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}.

Pentru ca parlamentarii din Ferentari nu au rabdare cu el (si a fost chemat si la diplomatii din Pantelimon pentru ziua urmatoarea) el vrea doar restul raspunsului la aceasta intrebare la impartirea cu R (o valoare data de parlamentari) si in plus vrea sa afle raspunsul pentru T valori date ale lui N.

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.

h2. Date de intrare