anticip

Un sumator pe un bit este un mic dispozitiv cu $3$ intrări şi $2$ ieşiri. El primeşte la intrare $X_1$, $X_2$ şi $T_i$. $X_1$ şi $X_2$ sunt biţii ce trebuie adunaţi, iar $T_i$ este transportul anterior (ca intrare). La ieşire furnizează $Y$ şi $T_o$. $Y$ este suma, iar $T_o$ este transportul următor (ca ieşire). Pentru a formaliza aceste lucruri putem scrie:

$Y = (X_1 + X_2 + T_i) \ mod \ 2$ (mod este restul împărţirii întregi)
$T_o = (X_1 + X_2 + T_i) \ div \ 2$ (div este câtul împărţirii întregi)

Pentru a aduna numere pe $N$ biţi se folosesc $N$ astfel de sumatoare. Ele sunt legate ca în figura de mai jos, adică transportul de ieşire al unui sumator este transportul de intrare pentru următorul.

Problema cu aceste sumatoare pe mai multi biţi este că un sumator trebuie să aştepte transportul de la unitatea anterioară (exceptând primul sumator).
Dacă unui sumator pe un bit face calculul într-o secundă, atunci pentru un sumator pe $N$ biţi (format din $N$ sumatoare pe un bit) vor fi necesare $N$ secunde.
Pentru a îmbunătăţi performanţa acestor sumatoare pe $N$ biţi s-au introdus nişte unităţi capabile să anticipeze transportul, adică intrarea $T_i$. Aceste unităţi verifică datele de intrare precedente $X_1 (i-1)$ şi $X_2 (i-1)$. Dacă amândouă sunt $0$ atunci $T_i$ va fi $0$, indiferent de ce primeşte acea unitate ca transport de intrare. De asemenea dacă amândouă sunt $1$ atunci $T_i$ va fi $1$. Toate sumatoarele care folosind anticipaţia pot calcula transportul de la sumatorul precedent încep calculul odată cu primul sumator. Comunicarea transportului de la un sumator la următorul se realizează instantaneu.
Cercetătorii care au inventat aceste unităţi de transport vor să ştie cu cât îmbunătăţesc performanţa sistemului şi au hotărât să se facă toate adunările posibile, pentru a compara cu vechiul sistem. Prin toate adunările posibile se înţelege că se va aduna orice număr pe $N$ biţi cu orice număr pe $N$ biţi fix o dată (în total $4 \cdot N$ adunări). Ei vor să ştie cât au durat aceste operaţii, adică suma tuturor timpilor pentru fiecare adunare.

Cerinţă

Scrieţi un program care să determine numărul total de secunde necesare pentru toate adunările, folosind dispozitivele de anticipare.

Date de intrare

Fişierul de intrare anticip.in conţine o singură linie pe care se află numărul natural $N$ reprezentând numărul de biţi.

Date de ieşire

Fişierul de ieşire anticip.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de secunde necesare tuturor adunărilor posibile.

Restricţii şi precizări

• $0 < N < 51$
• Problema aceasta nu are nici o legătură cu vreun balaur.

Exemplu

anticip.in

3

anticip.out

128

Explicație

$16$ adunări se realizează într-o secundă; $32$ adunări se realizează în două secunde; $16$ adunări se realizează în trei secunde.
De exemplu, adunarea $010+001$ necesită $3$ secunde. Adunarea $010+000$ necesită $2$ secunde. Adunarea $010+110$ necesită o secundă (primul sumator adună biţii din dreapta).