| Fişierul intrare/ieşire: | tritzi.in, tritzi.out | Sursă | Happy Coding 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tritzi
Un trit este o unitate logica care poate lua 3 valori: 0, 1 si 2. Tritzii se pot folosi exact la fel ca si bitzii (despre care, probabil, ati auzit cu totzii). De exemplu, se pot transmite informatzii reprezentate sub forma unor siruri de tritzi. Pentru a nu se confunda cu sirurile de bitzi, sirurile de tritzi au o proprietate speciala : doi tritzi avand valorile 0 si respectiv 1 nu pot fi transmisi unul dupa altul. Astfel, exista siruri de tritzi valide si invalide (care contzin cel putzin o pereche de tritzi alaturatzi egali cu 0 si 1). De exemplu, sirul 02212212000211 este un sir valid, dar sirurile 0122212 sau 2221022 nu sunt valide.
Determinati numarul de siruri de tritzi valide, de lungime N. Intrucat acest numar poate fi foarte mare, ne intereseaza numai valoarea acestuia modulo un numar P.
Date de intrare
Pe prima linie a fisierului de intrare tritzi.in se afla numarul intreg T, reprezentand numarul de teste ce urmeaza. Urmatoarele T linii contzin cate 2 numere intregi: N si P.
Date de iesire
Pentru fiecare test din fisierul de intrare veti afisa in fisierul de iesire tritzi.out un numar reprezentand valoarea ceruta.
Restrictii
- 1 ≤ T ≤ 30
- 1 ≤ N ≤ 1 000 000 000
- 1 ≤ P ≤ 32 000
Exemplu
| tritzi.in | tritzi.out |
|---|---|
| 4 1 997 4 997 21 997 999999999 13 | 3 41 22 5 |
