A - Potenciales Palíndromos

Languages: C, C++, Java, Haskell, Pascal, 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