C - Let's Make a Palindrome

Contest Duration: 2023-03-27(Mon) 06:00 - 2023-03-27(Mon) 08:30 (local time) (150 minutes)

C - Let's Make a Palindrome Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $200$ 点

英小文字と ? のみからなる文字列 $S$ が与えられます。

文字列 $S$ に含まれる ? をそれぞれ好きな英小文字に置き換えることで作れる回文は何通りあるか求めてください。

ただし、答えは非常に大きくなる可能性があるので、 $998244353$ で割ったあまりを出力してください。

回文の定義

文字列 $T$ が回文であるとは、 $1 \leq i \leq | T |$ を満たすすべての整数 $i$ について、 $T$ の前から $i$ 文字目の文字と後ろから $i$ 文字目の文字が同じ文字であることをいいます。

入力は以下の形式で標準入力から与えられます。

$S$

答えを $998244353$ で割ったあまりを $1$ 行に出力してください。

Copy

a??

Copy

aaa、aba、aca など、全部で $26$ 通りの回文を作ることができます。

Copy

atcoder

Copy

回文を作ることはできません。

Copy

?????????????

Copy

45855352

答えを $998244353$ で割ったあまりを出力することに注意してください。