Problem
La granja de John está representada por una cuadrícula de N × N campos (2≤N≤18), cada uno etiquetado con una letra del alfabeto. Por ejemplo,
ABCD
BXZX
CDXB
WCBA
Todos los días, Besi, la vaca, va de la esquina superior izquierda a la inferior derecha, moviéndose una celda hacia la derecha o una celda hacia abajo. Besi escribe la cuerda que resulta de su ruta, construida a partir de las letras que caminó. Se molestará mucho si la cadena resultante resulta ser un palíndromo (se lee igual de principio a fin y de principio a fin), porque se confundirá en qué dirección se fue.
Ayuda a Besie a descubrir cuántos palíndromos diferentes puede formar durante su viaje. Las diferentes formas de formar el mismo palíndromo solo deben contarse una vez. Por ejemplo, en el ejemplo anterior, hay varias formas de formar el palíndromo ABXZXBA, pero solo hay 4 palíndromos diferentes que Besi puede formar ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
FORMATO DE ENTRADA:
La primera línea de entrada contiene N y las siguientes líneas N contienen N descripción del campo. Cada línea contiene N caracteres en el rango A..Z.
FORMATO DE SALIDA:
Imprime el número de palíndromos distintos que puede formar Besi.
| Entrada |
Salida |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |