對於一個由 A 與 B 組成的字串 $T$，定義 $f(T)$ 為最多可以執行以下操作的次數。

操作：移除一個作為 $T$ 的（不一定連續的）子序列出現的 ABA，並將留下的空隙接合起來。

給定一個由 A、B 與 ? 組成的字串 $S$。對於將 $S$ 中的每個 ? 分別替換為 A 或 B 所得到的所有字串 $T$，求 $f(T)$ 的總和，對 $998244353$ 取模。

輸入格式

輸入以以下格式給出：

$$S$$

$S$ 是一個由 A、B 與 ? 組成的字串，其長度介於 $3$ 到 $1000$ 之間（包含兩端）。

輸出格式

輸出答案。

範例

輸入格式 1

A?B?

輸出格式 1

2

輸入格式 2

?B?A?B?

輸出格式 2

15

輸入格式 3

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

輸出格式 3

4595728

說明

在第一個範例中，所有可能的字串 $T$ 及其對應的 $f(T)$ 值如下：

• $T = \texttt{AABA}$: $f(T) = 1$.
• $T = \texttt{AABB}$: $f(T) = 0$.
• $T = \texttt{ABBA}$: $f(T) = 1$.
• $T = \texttt{ABBB}$: $f(T) = 0$.

因此，答案為 $1 + 0 + 1 + 0 = 2$。