Fişierul intrare/ieşire:	sir2.in, sir2.out	Sursă	Lot 2006 Ploiesti
Autor	Alexandru Mosoi	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sir 2

Asupra unui sir format doar din cifrele 1, 2 si 3 se aplica o transformare T, prin aplicarea simultana a urmatoarelor 3 operatii:

1. O secventa maximala formata din n de 1 consecutivi se transforma in n1
   De exemplu:
   • 1 se transforma in 11
   • 11 se transforma in 21
   • 111 se transforma in 31
2. O secventa maximala formata din n de 2 consecutivi se transforma in n2
   De exemplu:
   • 2 se transforma in 12
   • 22 se transforma in 22
   • 222 se transforma in 32
3. Un 3 se transforma in 13
   De exemplu:
   • 3 se transforma in 13
   • 33 se transforma in 1313
   • 333 se transforma in 131313

De exemplu:

• T(3113) = 132113
• T(3) = 13
• T(1331) = 11131311

Sa consideram sirul S definit prin recurenta astfel: S₁ = 3 si S_k = T(S_k-1), k > 1.

Cerinta

Se da N un numar natural, sa se determine lungimea sirului S_N. Pentru ca lungimea poate fi foarte mare se cere afisarea rezultatului modulo 37781.

Date de intrare

In fisierul de intrare sir2.in se afla pe prima linie numarul natural N.

Date de iesire

Fisierul de iesire sir2.out va contine o singura linie pe care veti scrie lungimea lui SN modulo 37781.

Restrictii

• S_i va fi format numai din 1, 2 si 3 pentru orice i > 0
• 0 < N < 2⁶⁰

Exemplu

Explicatie

Primii termeni ai sirului S sunt: 3, 13, 1113, 3113, 132113, 1113122113, 311311222113, etc.

Cum se trimit solutii?