On définit un Ketek comme une phrase qui se lit de la même manière de gauche à droite et de droite à gauche, mot par mot. Par exemple, « fall leaves after leaves fall » est un Ketek car les mots dans l'ordre inverse sont les mêmes que dans l'ordre original.

Étant donné une chaîne composée de lettres minuscules et du caractère « ? », comptez le nombre de Keteks distincts que vous pouvez former en remplaçant chaque « ? » par des lettres minuscules (une lettre par « ? »), et en ajoutant éventuellement des espaces entre les lettres. Notez qu'un Ketek ne peut contenir aucun « ? » ; ils doivent tous être remplacés exclusivement par des lettres minuscules.

Par exemple, si nous commençons avec la chaîne « ababa », nous pouvons former 3 Keteks différents : « ababa », « a bab a » et « a b a b a ».

Si nous commençons avec la chaîne « ?x?z » à la place, nous pouvons former 703 Keteks différents :

• Il y a $26^2 = 676$ façons de remplacer les « ? » et de former un Ketek composé d'un seul mot.
• Ajoutez des espaces pour former « ? x? z ». Il y a 26 façons de former un Ketek (le premier « ? » doit être z ; l'autre peut être n'importe quelle lettre minuscule).
• Ajoutez un espace pour former « ?x ?z ». Il n'y a aucun moyen de former un Ketek.
• Ajoutez des espaces pour former « ? x ? z ». Il y a une façon de former un Ketek (le premier « ? » doit être z ; le second doit être x).

Le total est $676 + 26 + 0 + 1 = 703$.

Deux Keteks sont différents s'ils ont un nombre de mots différent, ou s'il existe un indice de mot où les mots ne sont pas les mêmes.

Entrée

La ligne unique d'entrée contient une chaîne $s$ ($1 \le |s| \le 30\,000$), qui consiste en des lettres minuscules (« a » – « z ») et le caractère « ? ».

Sortie

Affichez le nombre de Keteks distincts qui peuvent être formés en remplaçant les « ? » par des lettres minuscules et en ajoutant des espaces. Comme ce nombre peut être grand, affichez-le modulo $998\,244\,353$.

Exemples

Entrée 1

ababa

Sortie 1

3

Entrée 2

?x?z

Sortie 2

703