Problem E
Ketek Counting
Define a Ketek to be a sentence that reads the same forwards and backwards, by word. For example, ‘fall leaves after leaves fall’ is a Ketek since the words in reverse order are the same as the original order.
Given a string consisting of lowercase letters and the character ‘?’, count the number of distinct Keteks you can make by replacing every ‘?’ with lowercase letters (one letter per ‘?’), and optionally adding spaces between any letters. Note that a Ketek cannot contain any ?’s; they all must be replaced exclusively by lowercase letters.
For example, if we start with the string ‘ababa’, we can form 3 different Keteks: ‘ababa’, ‘a bab a’ and ‘a b a b a’.
If we start with the string ‘?x?z’ instead, we can form 703 different Keteks:

There are $26^2 = 676$ ways to replace the ?’s and form a oneword Ketek.

Add spaces to form ‘? x? z’. There are $26$ ways to form a Ketek (the first ‘?’ must be z; the other can be any lowercase letter).

Add a space to form ‘?x ?z’. There is no way to form a Ketek.

Add spaces to form ‘? x ? z’. There is one way to form a Ketek (the first ‘?’ must be z; the second must be x).
The total is $676 + 26 + 0 + 1 = 703$.
Two Keteks are different if they have a different number of words, or there is some word index where the words are not the same.
Input
The single line of input contains a string $s$ ($1 \le s \le 30\, 000$), which consists of lowercase letters (‘a’–‘z’) and the character ‘?’.
Output
Output the number of distinct Keteks that can be formed by replacing the ?’s with lowercase letters and adding spaces. Since this number may be large, output it modulo $998\, 244\, 353$.
Sample Input 1  Sample Output 1 

ababa 
3 
Sample Input 2  Sample Output 2 

?x?z 
703 