|
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.
A - Potenciales Palíndromos
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Se tiene una cadena de caracteres, donde en algunas posiciones aparece el símbolo $\texttt{?}$. El objetivo en este problema es sencillo: Calcular el número de palíndromos que se pueden formar cambiando esos símbolos por letras minúsculas cualesquiera del alfabeto latino.
Input
La primera línea de la entrada consiste en un número entero $T$ ($1 \leq T \leq 20$) que indica la cantidad de casos que siguen. Cada caso está representado por una línea que contiene el string en cuestión. Se puede asumir que la suma de las longitudes de todos los strings es menor que $10^6$.
Output
Por cada caso se debe imprimir la cantidad de palíndromos que se pueden formar cambiando los caracteres $\texttt{?}$ por letras minúsculas del alfabeto latino. Como este número puede ser muy grande se debe calcular el resto de su división por $10000009$.
Sample test(s)
Input
5
?
??
ab?
a?c
aba
Output
26
26
1
0
1