OffRoad

Cerință

Ni se da geografia unui loc sub forma unei matrici de $N$ x $N$. Matricea are caractere litere mici englezesti $a...z$ si reprezinta inaltimile terenului de la o pozitie, $a$ este vale de exemplu si $z$ munte.

Suntem cu masina la o sesiune de off road si vrem sa ajungem din coordonata $(i_M,j_M)$ la un target care e la coordonatele $(i_T,j_T)$.

Masina se poate misca dintr-o casuta la orice alta casuta cu care are o latura comuna, dar trebuie sa tinem cont de faptul ca putem shimba inaltimea la care suntem maxim o data, altfel masina se strica de la cazaturi (sau urcusuri).

In cate moduri putem alege valorile $i_M,j_M,i_T,j_T$, astfel încât să putem ajunge la target (sa avem un sesh reusit)?

Date de intrare

Pe prima linie este $N$ iar in continuare va fi dat teremnul.

Date de ieșire

Numarul de moduri in care putem avea un sesh reusit.

Restricții și precizări

• $1 \leq N \leq 1000$
• Pozitia de inceput trebuie sa fie diferita de pozitia targetului
• Pentru 20p $1 \leq N \leq 50$

Exemplul 1

stdin

3
aab
abc
ccc

stdout

70

Explicație

Daca punem masina pe pozitia $(1,1)$ putem pune targetul oriunde si vom putea ajunge la el schimband inaltimea maxim o data.
Daca putem masina pe pozitia $(1,3)$ in schimb vom putea pune targetul doar pe $7$ pozitii.

Exemplul 2

stdin

5
aabcb
abbcb
aabbb
ccccc
abbcd

stdout

430