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

Alinut a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Cu 5 minute inainte de a da drumul la mixer si-a dat seama ca in realitate el nu cunoaste decat $2$ melodii (prima dureaza $1$ minut, iar a doua $2$ minute), dar a fost chemat pentru exact $N$ minute de spectacol. Deoarece Alinut este student la FMI si nu la Conservator si in plus nu prea mai are timp la dispozitie, acest lucru nu il deranjeaza prea mult, dar este curios sa stie pentru cele $N$ minute de reprezentatii care este numarul de moduri diferite de a dispune cele $2$ melodii astfel incat reprezentatia sa dureze exact cele N minute. De exemplu pentru $N = 4$ minute, el are la dispozitie $5$ posibilitati de dispunere a melodiilor : $1, 1, 1, 1 ; 1, 1, 2 ; 1, 2, 1 ; 2, 1, 1 ; 2, 2$.

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.

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

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.

Pe prima linie a fişierului de intrare $melodii.in$ se vor gasi valorile $T$ si $R$ cu semnificatia de mai sus.
Pe fiecare din urmatoarele $T$ linii se va afla exact o singura valoare ce va semnifica numarul $N$ de minute pentru testul respectiv.

h2. Date de ieşire

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

În fişierul de ieşire $melodii.out$ se vor afisa exact $T$ linii. Pe a $i$-a linie se va afla raspunsul pentru a $i$-a intrebare din fisierul de intrare.

h2. Restricţii

* $1 ≤ T, R ≤ 100 000$
* $1 ≤ N ≤ 10^18

* $1 ≤ T ≤ 100 000$
* $3 ≤ R ≤ 100 000$
* $1 ≤ N ≤ 10^18^$

* Pentru $50%$ din teste, $1 ≤ N ≤ 1 000 000$

* Doua subsecvente de melodii a ~1~, a ~2~, ... a ~k~ si b ~1~, b ~2~, ... b ~m~ se considera distincte, daca $k$ ≠ $m$ sau exista un $i$ astfel incat a ~i~ ≠ b ~i~.
* $R$ nu este neaparat un numar prim

h2. Exemplu
table(example). |_. melodii.in |_. melodii.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 5
  1
  2
  3
  10
  666013
| 1
  2
  3
  4
  2

|
h3. Explicaţie

...
 

Pentru $N$ = $1$ se poate reda doar melodia care dureaza $1$ minut.
Pentru $N$ = $2$ sunt $2$ moduri de dispunere a melodiilor : $1, 1 ; 2$.
Pentru $N$ = $3$ sunt $3$ moduri: $1, 1 , 1 ; 2, 1 ; 1, 2$.
Pentru $N$ = $10$ sunt $89$ de moduri, iar raspunsul este $89 **modulo** 5 = 4$.
 

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

9220