sir

Asupra unui şir format doar din cifrele $1, 2$ şi $3$ se aplică o transformare $T$, prin aplicarea simultană a următoarelor $3$ operaţii:

1. O secvenţă maximală formată din $n$ de $1$ consecutivi se transformă în $n1$
   De exemplu:
   • $1$ se transformă în $11$
   • $11$ se transformă în $21$
   • $111$ se transformă în $31$
2. O secvenţă maximală formată din $n$ de $2$ consecutivi se transformă în $n2$
   De exemplu:
   • $2$ se transformă în $12$
   • $22$ se transformă în $22$
   • $222$ se transformă în $32$
3. Un $3$ se transformă în $13$
   De exemplu:
   • $3$ se transformă în $13$
   • $33$ se transformă în $13 \ 134$
   • $333$ se transformă în $1 \ 313 \ 134$

De exemplu:
$T(3 \ 113) = 132 \ 113$
$T(3) = 13$
$T(1 \ 331) = 11 \ 131 \ 311$

Să considerăm şirul $S$ definit prin recurenţă astfel: $S_1 = 3$ si $S_k = T(S_k-1), k > 1$.

Cerinţă

Se dă $N$ un număr natural, să se determine lungimea şirului $S_N$. Pentru că lungimea poate fi foarte mare se cere afişarea rezultatului modulo $37 \ 781$.

Date de intrare

În fişierul de intrare sir.in se află pe prima linie numărul natural $N$.

Date de ieşire

Fişierul de ieşire sir.out va conţine o singură linie pe care veţi scrie lungimea lui $S_N$ modulo $37 \ 781$.

Restricţii şi precizări

• $S_i$ va fi format numai din $1, 2$ şi $3$ pentru orice $i>0$.
• $1 \leq N < 260$

Exemplul 1

sir.in

1

sir.out

1

Exemplul 2

sir.in

6

sir.out

10

Exemplul 3

sir.in

71

sir.out

13391

Explicație

Primii termeni ai şirului $S$ sunt: $3$, $13$, $1 \ 113$, $3 \ 113$, $132 \ 113$, $1 \ 113 \ 122 \ 113$, $311 \ 311 \ 222 \ 113$, etc.