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

操作：刪走一個作為 $T$ 嘅（唔一定連續嘅）子序列出現嘅 ABA，然後將留低嘅空位駁返埋一齊。

俾你一個由 A、B 同 ? 組成嘅字串 $S$。對於將 $S$ 入面嘅每個 ? 分別替換成 A 或者 B 所得到嘅所有字串 $T$，求 $f(T)$ 嘅總和，對 $998244353$ 取模。

輸入格式

輸入會用以下格式俾出：

$$S$$

$S$ 係一個由 A、B 同 ? 組成嘅字串，長度喺 $3$ 到 $1000$ 之間（包括頭尾）。

輸出格式

輸出答案。

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 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$。