对于一个由 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$。