Fişierul intrare/ieşire:tritzi.in, tritzi.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.2 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/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.intritzi.out
4
1 997
4 997
21 997
999999999 13
3
41
22
5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content