Problem
La fattoria di John è rappresentata da una griglia di N×N campi (2≤N≤18), ciascuno etichettato con una lettera dell'alfabeto. Ad esempio,
ABCD
BXZX
CDXB
WCBA
Ogni giorno la mucca Besi va dall'angolo in alto a sinistra a quello in basso a destra, spostandosi di una cella a destra o di una cella in basso. Besi annota il filo che risulta dal suo percorso, costruito con le lettere che ha percorso. Sarà molto turbata se la stringa risultante risulta essere un palindromo (si legge lo stesso dall'inizio alla fine e dalla fine all'inizio), perché si confonderà in quale direzione è andata.
Aiuta Besie a capire quanti diversi palindromi può formare durante il suo viaggio. Modi diversi per formare lo stesso palindromo dovrebbero essere contati una sola volta. Ad esempio, nell'esempio sopra, ci sono diversi modi per formare il palindromo ABXZXBA, ma ci sono solo 4 diversi palindromi che Besi può formare ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
FORMATO DI IMMISSIONE :
La prima riga di input contiene N e le successive N righe contengono N < /strong> descrizione del campo. Ogni riga contiene N caratteri nell'intervallo A..Z.
FORMATO DI USCITA :
Stampa il numero di palindromi distinti che Besi può formare.
| Input |
Uscita |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |