== include(page="template/taskheader" task_id="sir2") ==

Poveste si cerinta...

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: $S1$ = $3$ si $Sk$ = T(Sk-1), k > 1.
 
h2. Cerinta
 
Se da $N$ un numar natural, sa se determine lungimea sirului SN. Pentru ca lungimea poate fi foarte mare se cere afisarea rezultatului modulo {**$37781$**}.

h2. Date de intrare

Fisierul de intrare $sir2.in$ ...

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

h2. Date de iesire

In fisierul de iesire $sir2.out$ ...

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

h2. Restrictii

* $... ≤ ... ≤ ...$

* S ~i~ va fi format numai din $1$, $2$ si $3$ pentru orice $i$ > $0$ .
* 0 < N < $2^60^$
 

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

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

| 1
| 1

|

| 6
| 10
|
| 71
| 13391
|

h3. Explicatie

...

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

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