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$ です。