Zdefiniujmy Ketek jako zdanie, które czyta się tak samo od przodu i od tyłu, patrząc na słowa. Na przykład „fall leaves after leaves fall” jest Ketekiem, ponieważ słowa w odwrotnej kolejności tworzą ten sam ciąg co w kolejności oryginalnej.

Mając dany ciąg znaków składający się z małych liter alfabetu angielskiego oraz znaku „?”, oblicz liczbę różnych Keteków, które można utworzyć, zastępując każdy znak „?” małą literą (jedna litera na każdy znak „?”) i opcjonalnie dodając spacje pomiędzy dowolnymi literami. Zauważ, że Ketek nie może zawierać żadnych znaków „?”; wszystkie muszą zostać zastąpione wyłącznie małymi literami.

Na przykład, jeśli zaczniemy od ciągu „ababa”, możemy utworzyć 3 różne Keteki: „ababa”, „a bab a” oraz „a b a b a”.

Jeśli zamiast tego zaczniemy od ciągu „?x?z”, możemy utworzyć 703 różne Keteki:

• Istnieje $26^2 = 676$ sposobów na zastąpienie znaków „?” i utworzenie jednowyrazowego Keteka.
• Dodając spacje, aby utworzyć „? x? z”, istnieje 26 sposobów na utworzenie Keteka (pierwszy znak „?” musi być z; drugi może być dowolną małą literą).
• Dodając spację, aby utworzyć „?x ?z”, nie ma możliwości utworzenia Keteka.
• Dodając spacje, aby utworzyć „? x ? z”, istnieje jeden sposób na utworzenie Keteka (pierwszy znak „?” musi być z; drugi musi być x).

Suma wynosi $676 + 26 + 0 + 1 = 703$.

Dwa Keteki są różne, jeśli mają różną liczbę słów lub jeśli istnieje indeks słowa, dla którego słowa te nie są identyczne.

Wejście

Pojedyncza linia wejścia zawiera ciąg znaków $s$ ($1 \le |s| \le 30\,000$), który składa się z małych liter („a” – „z”) oraz znaku „?”.

Wyjście

Wypisz liczbę różnych Keteków, które można utworzyć poprzez zastąpienie znaków „?” małymi literami i dodanie spacji. Ponieważ liczba ta może być duża, wypisz ją modulo 998 244 353.

Przykład

Wejście 1

ababa

Wyjście 1

3

Wejście 2

?x?z

Wyjście 2

703