melodii

Melodii

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

Poveste şi cerinţă...

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.
 
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}.
 
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.

h2. Date de intrare

Fişierul de intrare $melodii.in$ ...

Pe prima linie din fişierul de intrare $melodii.in$ se vor gasi valorile $T$ si $R$. Pe urmatoarele T linii se va afla exact o singura valoarea ce va semnifica numarul N de minute pentru testul respectiv.

h2. Date de ieşire

În fişierul de ieşire $melodii.out$ ...

În fişierul de ieşire $melodii.out$ se vor afla exact $T$ linii, raspunsul la cele $T$ intrebari in ordinea in care se gasesc in fisierul de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T, R ≤ 100 000$
* $1 ≤ N ≤ 10^18
* Pentru $50%$ din teste, $1 ≤ N ≤ 1 000 000$

h2. Exemplu