Cerința

Pentru a-i duce cadoul dorit lui Dorel, Moș Crăciun trebuie să străbată un labirint cu capcane reprezentat de o matrice cu n linii și n coloane. Fiecare celula a labirintului este marcată cu valoarea 1 dacă este capcană sau cu 0 dacă este poziție liberă. Inițial, Moș Crăciun se află în celula de coordonate (1, 1), iar Dorel în celula de coordonate (n,n).

Moș Crăciun se poate deplasa doar pe valori vecine pe diagonale. Dacă se află în poziția (i,j), atunci el poate merge în pozițiile (i-1,j-1), (i-1,j+1), (i+1,j+1) și (i+1,j-1).

Moș Crăciun dorește să știe numărul total de drumuri pe care le poate urma prin labirint până la poziția în care se află Dorel, astfel încât să nu treacă prin capcane și să nu treacă de mai multe ori prin aceeași pozitie. De asemenea, Moș Crăciun vrea să îl facă pe Dorel să îl aștepte cât mai mult și ar vrea să știe lungimea celui mai lung drum. Dacă îl ajutați să calculeze aceste numere, atunci Moș Crăciun promite că va trece și pe la voi.

Date de intrare

Se citește de la tastatură numărul n, iar de pe următoarele n linii câte n valori de 0 sau 1 cu semnificația din enunț, separate prin câte un spațiu.

Date de ieșire

Se va afișa pe ecran numărul de moduri în care poate ajunge Moș Crăciun din poziția inițială în poziția unde îl așteaptă Dorel. Pe linia următoare se va scrie numărul de celule din care este format cel mai lung drum.
Dacă Moș Crăciun nu poate ajunge la Dorel, atunci se va afișa mesajul Dorel :((

Restricții și precizări

• 1 ≤ n ≤ 10
• pozițiile (1,1) și (n,n) nu sunt capcane

Exemplu:

Intrare

5
0 1 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0

Ieșire

4
9

Explicație

Cele 4 drumuri posibile sunt:

1 1 1 0 0
1 2 0 0 0
0 1 3 0 0
0 0 0 4 1
0 0 1 0 5 

1 1 1 0 0
1 2 0 4 0
0 1 3 0 5
0 0 0 6 1
0 0 1 0 7

1 1 1 0 0
1 2 0 0 0
3 1 5 0 0
0 4 0 6 1
0 0 1 0 7

şi

1 1 1 0 0
1 2 0 6 0
3 1 5 0 7
0 4 0 8 1
0 0 1 0 9

Ultimul este traseul format din cele mai multe celule, adică 9.