「Ketek」とは、単語単位で前から読んでも後ろから読んでも同じになる文のことである。例えば、「fall leaves after leaves fall」は、単語を逆順に並べても元の順序と同じになるため、Ketek である。

小文字と文字「?」からなる文字列が与えられる。すべての「?」を小文字に置き換え（「?」1つにつき1文字）、必要に応じて文字間にスペースを追加することで作成できる、異なる Ketek の総数を求めよ。なお、Ketek に「?」を含めることはできず、すべて小文字に置き換えなければならない。

例えば、文字列「ababa」から開始する場合、3つの異なる Ketek「ababa」、「a bab a」、「a b a b a」を作成できる。

文字列「?x?z」から開始する場合、703通りの異なる Ketek を作成できる。

• 「?」を置き換えて1単語の Ketek を作る方法は $26^2 = 676$ 通りある。
• スペースを追加して「? x? z」という形にする。Ketek を作る方法は 26 通りある（最初の「?」は z でなければならず、もう一方は任意の小文字でよい）。
• スペースを追加して「?x ?z」という形にする。Ketek を作る方法はない。
• スペースを追加して「? x ? z」という形にする。Ketek を作る方法は 1 通りある（最初の「?」は z、2番目は x でなければならない）。

合計は $676 + 26 + 0 + 1 = 703$ となる。

2つの Ketek は、単語数が異なる場合、またはある単語のインデックスにおいて単語が異なる場合に、異なるとみなされる。

入力

入力は1行で、小文字（'a' – 'z'）と文字「?」からなる文字列 $s$ ($1 \le |s| \le 30\,000$) が与えられる。

出力

「?」を小文字に置き換え、スペースを追加することで作成できる異なる Ketek の総数を出力せよ。この数は非常に大きくなる可能性があるため、998 244 353 で割った余りを出力せよ。

入出力例

入力 1

ababa

出力 1

3

入力 2

?x?z

出力 2

703