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

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

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.

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 ≤ 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

| 1
  2
  3

  10
  x

  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