braduti

Robotul Vasile s-a angajat la fabrica decoraţiunilor de Crăciun unicat. El trebuie să monteze beculeţe colorate în brăduţi, astfel încât oricare doi brăduţi să fie diferiţi.
Pe o bandă de asamblare robotul Vasile are la dispoziţie $N$ beculeţe colorate $b_1 b_2 \dots b_N$, astfel încât oricare două beculeţe sunt colorate diferit. În vârful bradului va pune o steluţă, iar pentru montarea beculeţelor în brăduţ el construieşte lanţuri de becuri în modul următor:

• pentru primul lanţ selectează $3$ beculeţe $b_{i_1} \ b_{i_2} \ b_{i_3}$, în ordinea în care acestea sunt plasate pe bandă ($i_1 < i_2 < i_3$) şi montează în $b_{i_2}$ pe tulpina bradului, $b_{i_1}$ în stânga, iar $b_{i_3}$ în dreapta;
• pentru al doilea lanţ selectează apoi $5$ beculeţe $b_{j_1} \ b_{j_2} \ b_{j_3} \ b_{j_4} \ b_{j_5}$, în ordinea de pe bandă ($j_1 < j_2 < j_3 < j_4 < j_5$) şi montează $b_{j_3}$ pe tulpina bradului imediat sub $b_{i_2}$, în stânga $b_{j_1}$ şi $b_{j_2}$ (în această ordine), iar în dreapta $b_{j_4}$ şi $b_{j_5}$ (în această ordine);
• continuă în acelaşi mod, construind la fiecare pas un lanţ în care se selectează două becuri în plus faţă de lanţul precedent, respectând ordinea în care se află becurile pe banda de asamblare; becul situat la mijlocul lanţului este montat pe tulpină, imediat sub becul precedent, celelalte becuri fiind plasate în ordine în partea stângă, respectiv în partea dreaptă;
• procedeul se repetă până când numărul de becuri rămase pe banda de asamblare este insuficient pentru construirea unui nou lanţ.

Înălţimea bradului este considerată egală cu numărul de lanţuri construite (egal cu numărul de beculeţe montate pe tulpină). Doi brazi sunt diferiţi dacă există cel puţin o poziţie în care în cei doi brazi se află beculeţe de culori diferite.

Cerințe

Cunoscând numărul $N$ de beculeţe aflate pe banda de asamblare, scrieţi un program care să rezolve următoarele două cerinţe:

1. determină înălţimea bradului (numărul de lanţuri ce pot fi construite cu cele $N$ beculeţe);
2. determină numărul de brazi diferiţi ce pot fi construiţi cu cele $N$ beculeţe.

Date de intrare

Fişierul de intrare braduti.in conţine pe prima linie numărul $C$ care reprezintă cerinţa care trebuie să fie rezolvată ($1$ sau $2$). Pe a doua linie se află numărul natural $N$ care reprezintă numărul de beculeţe colorate de pe linia de asamblare.

Date de ieșire

Fişierul de ieşire braduti.out va conţine o singură linie pe care va fi scris un număr natural reprezentând rezultatul determinat pentru cerinţa $C$.

Restricții și precizări

• $3 \leq N \leq 5 \ 555$
• Pentru teste valorând $10$ puncte $C=1$
• Pentru teste valorând $20$ de puncte, $C=2$ şi rezultatul va avea cel mult $18$ cifre
• Pentru teste valorând $60$ de puncte, $C=2$ şi rezultatul va avea cel mult $10 \ 000$ cifre
• $10$ puncte se acordă din oficiu.

Exemplul 1

braduti.in

1
17

braduti.out

3

Explicație

Se va rezolva cerința $1$. Numărul de lanţuri ce pot fi construite cu $17$ beculeţe este $3$. Beculeţele vor fi aranjate ca în desen.

Exemplul 2

braduti.in

2
17

braduti.out

49008960

Explicație

Se va rezolva cerința $2$. Se determină numărul de brăduţi diferiţi ce pot fi construiţi cu $17$ beculeţe.

Exemplul 3

braduti.in

2
5

braduti.out

10

Explicație

Se va rezolva cerința $2$. Se determină numărul de brăduţi diferiţi ce pot fi construiţi cu $5$ beculeţe.