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 1313
• 333 se transformă în 131313
De exemplu: T(3113) = 132113
T(3) = 13
T(1331) = 11131311
Să considerăm şirul S definit prin recurenţă astfel: S1 = 3 si Sk = T(Sk-1), k > 1.
Cerinţă
Se dă N un număr natural, să se determine lungimea şirului SN. Pentru că lungimea poate fi foarte mare se cere afişarea rezultatului modulo 37781.
Date de intrare
În fişierul de intrare sir5.in se află pe prima linie numărul natural N.
Date de ieşire
Fişierul de ieşire sir5.out va conţine o singură linie pe care veţi scrie lungimea lui SN modulo 37781.
Restricţii
Si va fi format numai din 1, 2 şi 3 pentru orice i>0.
1 ≤ N < 260
Exemple
sir5.in
sir5.out
Explicaţii
6
10
Primii termeni ai şirului S sunt: 3, 13, 1113, 3113, 132113, 1113122113, 311311222113, etc.