== include(page="template/taskheader" task_id="sir2") ==
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$

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

* {$T(3113) = 132113$}
* {$T(3) = 13$}
* {$T(1331) = 11131311$}
 
Sa consideram sirul $S$ definit prin recurenta astfel: {$S{~1~}$} = $3$ si {$S{~k~} = T(S{~k-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$**}.

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

h2. Date de intrare

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

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

h2. Date de iesire

h2. Restrictii

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

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

h2. Exemplu

h3. Explicatie

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

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