hike

Profesorul de informatică este recunoscut pentru două lucruri: problemele pe care le dă la clasă și pasiunea sa extremă pentru drumețiile montane. El susține mereu că, pentru a rezista la cele 4 ore de concentrare de la olimpiadă, ai nevoie de un fizic de fier și de mult aer curat. Așa că, înainte de vacanța de vară, el duce toți elevii de la mate-info într-o excursie.

Pentru a face lucrurile mai „interesante”, proful nu v-a dus pe un munte obișnuit. A folosit cunoștințele sale de generare procedurală a reliefului pentru a vă transpune într-o simulare virtuală a unui parc național de pe un plan bidimensional infinit.

El v-a explicat cum funcționează lumea lui:
„Vedeți voi, dragi elevi, altitudinea acestui munte infinit este definită de un șablon, o matrice de dimensiune $n \times n$ pe care am notat-o cu $h$. Acest șablon se repetă periodic la nesfârșit în toate direcțiile. Mai exact, pentru orice numere întregi $a$ și $b$, și pentru orice $x, y$ astfel încât $0 \le x, y < n$, altitudinea la coordonatele $(x + a \cdot n, y + b \cdot n)$ va fi exact $h[x][y]$!”

Când vă aflați la o poziție de coordonate $(x, y)$, vă puteți deplasa doar într-una dintre cele patru direcții cardinale, ajungând într-o poziție adiacentă: $(x, y + 1)$, $(x + 1, y)$, $(x, y - 1)$ sau $(x - 1, y)$.

Deoarece purtați rucsacuri grele pline cu laptopuri, efortul depus (măsurat în secunde) pentru a vă muta între două poziții adiacente depinde de diferența de nivel. Mai exact, timpul necesar este $1 + |\text{alt}_1 - \text{alt}_2|$, unde $\text{alt}_1$ și $\text{alt}_2$ sunt altitudinile poziției curente, respectiv ale poziției destinație.

Pornind de la tabăra de bază situată la coordonatele $(0, 0)$, proful se uită la ceas, zâmbește larg și vă lansează o provocare teoretică demnă de o eternitate:
„Timpul este relativ, dar să spunem că ați avea la dispoziție exact $10^{20}$ secunde de drumeție. Câte poziții distincte de pe acest plan infinit ați putea vizita în acest interval uriaș de timp?”

Răspunsul vostru va fi considerat corect dacă eroarea sa relativă față de răspunsul exact al profului este mai mică de $10^{-6}$.

Date de intrare

Prima linie conține un număr întreg $n$ — dimensiunea matricei care descrie altitudinile.

Următoarele $n$ linii conțin câte $n$ numere întregi. Al $(j + 1)$-lea număr de pe a $(i + 1)$-a linie dintre acestea este $h[i][j]$ — altitudinea poziției de bază $(i, j)$.

Date de ieșire

Afișați numărul de poziții distincte în care puteți ajunge într-un timp de cel mult $10^{20}$ secunde.

Restrictii si precizari

• $2 \le n \le 20$
• $0 \le h[i][j] \le 1545$
• Răspunsul va fi acceptat dacă eroarea relativă este mai mică de $10^{-6}$. Se recomandă afișarea rezultatului în notație științifică.

Exemplul 1

stdin

2
3 3
3 3

stdout

2e+40

Exemplul 2

stdin

3
0 0 0
0 1545 0
0 0 0

stdout

2e+40

Exemplul 3

stdin

4
0 1 2 3
5 6 7 4
10 11 8 9
15 12 13 14

stdout

1.524886878e+39