Summer FLASG Beginner | Telefonul

ASG și-a luat un telefon nou de la magazinul din colțul străzii. Era un Nokia vechi cu butoane. L-a desfăcut și l-a pus lângă birou și a mers să se joace Fortnite cu niște prieteni, însă și-a luat bătaie atât de tare încât, de nervi, a spart telefonul de masă. Astfel, pe telefonul lui se pot vedea acum doar steluțe. ASG, fiind băiat deștept, a observat o regula de creare. Telefonul a generat un anume număr de linii, iar numerele de stele de pe fiecare linie sunt, de la prima la ultima, numere Fibonacci consecutive.

Cerință

Dânduse un astfel de desen, să se determine dacă ar putea apărea sau nu pe telefonul lui ASG.

Date de intrare

Pe prima linie se găsește un singur număr natural $N$, numărul de linii al desenului.
Pe următoarele $N$ linii se vor găsi un anumit număr de steluțe *.

Date de ieșire

Dacă steluțele pot fi afișate pe telefonul lui ASG se va afișa DA, altfel NU.

Restricții și precizări

• $1 \leq N \leq 39$;
• $1 \leq$ numărul de steluțe de pe fiecare linie $\leq 63 \ 245 \ 986$.
• Un număr Fibonacci este suma celor doua numere de dinaintea lui. $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, iar de aici, $F_{i} = F_{i - 1} + F_{i - 2}$.
• Este garantat că, în afară de prima linie pe care se găsește numărul natural $N$, se vor afla doar steluțe pe toate celelalte linii.

Exemplul 1

stdin

3
*
*
**

stdout

DA

Explicație

$1$, $1$ și $2$ sunt, în ordine, numărul de steluțe de pe fiecare linie, iar acestea sunt numerele fibonacci de pe pozițiile $1$, $2$ și $3$.

Exemplul 2

stdin

2
****
******

stdout

NU

Explicație

Avem numerele $4$ și $6$. Acestea nu sunt numere Fibonacci consecutive (nici măcar nu sunt Fibonacci), așa că răspunsul este NU.