|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
G - Caminos palíndromos
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
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