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 b1, b2, …, bN, 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 bi1, bi2, bi3, în ordinea în care acestea sunt plasate pe bandă (i1 < i2 < i3) şi montează în bi2 pe tulpina bradului, bi1 în stânga, iar b3i în dreapta;
– pentru al doilea lanţ selectează apoi 5 beculeţe bj1, bj2, bj3, bj4, bj5, în ordinea de pe bandă (j1 < j2 < j3 < j4 < j5) şi montează bj3 pe tulpina bradului imediat sub bi2, în stânga bj1 şi bj2 (în această ordine), iar în dreapta bj4 şi bj5 (î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ța

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 ≤ N ≤ 5555
• 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ă pentru exemplele din enunț.

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.