Definimos un Ketek como una oración que se lee igual hacia adelante y hacia atrás, palabra por palabra. Por ejemplo, ‘fall leaves after leaves fall’ es un Ketek ya que las palabras en orden inverso son las mismas que en el orden original.
Dada una cadena que consiste en letras minúsculas y el carácter ‘?’, cuenta el número de Keteks distintos que puedes formar reemplazando cada ‘?’ con letras minúsculas (una letra por cada ‘?’), y opcionalmente añadiendo espacios entre cualesquiera letras. Ten en cuenta que un Ketek no puede contener ningún ‘?’; todos deben ser reemplazados exclusivamente por letras minúsculas.
Por ejemplo, si comenzamos con la cadena ‘ababa’, podemos formar 3 Keteks diferentes: ‘ababa’, ‘a bab a’ y ‘a b a b a’.
Si en cambio comenzamos con la cadena ‘?x?z’, podemos formar 703 Keteks diferentes:
- Hay $26^2 = 676$ formas de reemplazar los ‘?’ y formar un Ketek de una sola palabra.
- Añadir espacios para formar ‘? x? z’. Hay 26 formas de formar un Ketek (el primer ‘?’ debe ser z; el otro puede ser cualquier letra minúscula).
- Añadir un espacio para formar ‘?x ?z’. No hay forma de formar un Ketek.
- Añadir espacios para formar ‘? x ? z’. Hay una forma de formar un Ketek (el primer ‘?’ debe ser z; el segundo debe ser x).
El total es $676 + 26 + 0 + 1 = 703$.
Dos Keteks son diferentes si tienen un número diferente de palabras, o si existe algún índice de palabra donde las palabras no son las mismas.
Entrada
La única línea de entrada contiene una cadena $s$ ($1 \le |s| \le 30\,000$), la cual consiste en letras minúsculas (‘a’ – ‘z’) y el carácter ‘?’.
Salida
Imprime el número de Keteks distintos que se pueden formar reemplazando los ‘?’ con letras minúsculas y añadiendo espacios. Dado que este número puede ser grande, imprímelo módulo 998 244 353.
Ejemplos
Entrada 1
ababa
Salida 1
3
Entrada 2
?x?z
Salida 2
703