Problem 2186: 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

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