Определим «Кетек» (Ketek) как предложение, которое читается одинаково в обоих направлениях, если рассматривать его по словам. Например, «fall leaves after leaves fall» является Кетеком, так как слова в обратном порядке образуют ту же последовательность, что и в исходном.

Дана строка, состоящая из строчных латинских букв и символа «?». Подсчитайте количество различных Кетеков, которые можно получить, заменив каждый символ «?» на строчную латинскую букву (одна буква на каждый «?») и, при желании, добавив пробелы между любыми буквами. Заметьте, что Кетек не может содержать символов «?»; все они должны быть заменены исключительно на строчные буквы.

Например, если мы начнем со строки «ababa», мы можем сформировать 3 различных Кетека: «ababa», «a bab a» и «a b a b a».

Если мы начнем со строки «?x?z», мы можем сформировать 703 различных Кетека:

• Существует $26^2 = 676$ способов заменить «?» и сформировать однословный Кетек.
• Добавим пробелы, чтобы получить «? x? z». Существует 26 способов сформировать Кетек (первый «?» должен быть z; второй может быть любой строчной буквой).
• Добавим пробел, чтобы получить «?x ?z». Не существует способов сформировать Кетек.
• Добавим пробелы, чтобы получить «? x ? z». Существует 1 способ сформировать Кетек (первый «?» должен быть z; второй должен быть x).

Итого: $676 + 26 + 0 + 1 = 703$.

Два Кетека считаются различными, если они содержат разное количество слов или если существует индекс слова, на котором слова различаются.

Входные данные

Единственная строка входных данных содержит строку $s$ ($1 \le |s| \le 30\,000$), состоящую из строчных латинских букв («a» – «z») и символа «?».

Выходные данные

Выведите количество различных Кетеков, которые можно сформировать, заменяя «?» на строчные буквы и добавляя пробелы. Так как это число может быть очень большим, выведите его по модулю $998\,244\,353$.

Примеры

Входные данные 1

ababa

Выходные данные 1

3

Входные данные 2

?x?z

Выходные данные 2

703