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 文字目の文字が同じ文字であることをいいます。

制約

  • 1 \leq | S | \leq 200000
  • S は英小文字と ? のみからなる

入力

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

S

出力

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

入力例 1

a??

出力例 1

26

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

入力例 2

atcoder

出力例 2

0

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

入力例 3

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

出力例 3

45855352

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