G - Caminos palíndromos

Time limit: 2 seconds
Memory limit: 254 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Se tiene una matriz cuadrada de $N$ filas y columnas, en la que cada posición contiene una letra mayúscula del alfabeto latino. El objetivo es encontrar el número de caminos palíndromos que comienzan en $(1; 1)$ y terminan en $(N; N)$. Un camino es válido si en cada paso solo avanza una casilla a la derecha o una hacia abajo. Será además palíndromo si la concatenación de los caracteres en las posiciones que visita, forma una cadena palíndromo.

Input

La primera línea de la entrada es un entero $N (1 \leq N \leq 100)$ la cantidad de filas que tiene la matriz. Le siguen $N$ líneas, cada una con $N$ letras representando la matriz. Todas las letras son mayúsculas.

Output

La salida es un entero con la cantidad de caminos palíndromos. Como este número puede ser muy grande se debe imprimir el resto de su división por $1000000009$.

Sample test(s)

Input
3 ABA CBB ACA
Output
4