我們定義一個 Ketek 為一個以單字為單位，正讀與反讀皆相同的句子。例如，「fall leaves after leaves fall」是一個 Ketek，因為將其單字順序反轉後，與原句相同。

給定一個由小寫字母與字元 '?' 組成的字串，請計算透過將每個 '?' 替換為小寫字母（每個 '?' 對應一個字母），並選擇性地在任意字母之間加入空格，所能構成的相異 Ketek 數量。請注意，Ketek 不能包含任何 '?'；所有的 '?' 都必須被替換為小寫字母。

例如，若我們從字串 'ababa' 開始，我們可以構成 3 種不同的 Ketek：'ababa'、'a bab a' 以及 'a b a b a'。

若我們從字串 '?x?z' 開始，我們可以構成 703 種不同的 Ketek：

• 有 $26^2 = 676$ 種方式替換 '?' 並構成一個單字的 Ketek。
• 加入空格構成 '? x? z'。有 26 種方式構成 Ketek（第一個 '?' 必須是 z；另一個可以是任何小寫字母）。
• 加入空格構成 '?x ?z'。沒有任何方式可以構成 Ketek。
• 加入空格構成 '? x ? z'。有一種方式可以構成 Ketek（第一個 '?' 必須是 z；第二個必須是 x）。

總數為 $676 + 26 + 0 + 1 = 703$。

若兩個 Ketek 的單字數量不同，或者在某個單字索引處的單字不相同，則視為不同的 Ketek。

輸入格式

輸入僅包含一行字串 $s$ ($1 \le |s| \le 30\,000$)，由小寫字母 ('a' – 'z') 與字元 '?' 組成。

輸出格式

輸出透過替換 '?' 為小寫字母並加入空格所能構成的相異 Ketek 數量。由於此數字可能很大，請輸出其對 $998\,244\,353$ 取模後的結果。

範例

輸入 1

ababa

輸出 1

3

輸入 2

?x?z

輸出 2

703