|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||64 MB (추가 메모리 없음)||7||6||6||85.714%|
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 lower-case letters and the character '
?', count the number of distinct Keteks you can make by replacing every '
?' with lower-case 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 lower-case letters.
For example, if we start with the string '
ababa', we can form 3 different Keteks: '
a bab a' and '
a b a b a'.
If we start with the string '
?x?z' instead, we can form 703 different Keteks:
?'s and form a one-word Ketek.
? x? z'. There are $26$ ways to form a Ketek (the first '
?' must be
z; the other can be any lower-case letter).
?x ?z'. There is no way to form a Ketek.
? x ? z'. There is one way to form a Ketek (the first '
?' must be
z; the second must be
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.
The single line of input contains a string $s$ ($1 \le |s| \le 30\,000$), which consists of lower-case letters ('
z') and the character '
Output the number of distinct Keteks that can be formed by replacing the
?'s with lower-case letters and adding spaces. Since this number may be large, output it modulo $998\,244\,353$.