题目描述

对于一个仅由 A 和 B 组成的字符串 $T$，定义 $f(T)$ 为最多能够执行以下操作的次数。

操作： 删除 $T$ 中一个（不要求连续的）子序列 ABA，并将删除后留下的空隙合拢。

给定一个由 A、B 和 ? 组成的字符串 $S$。将 $S$ 中每个 ? 替换为 A 或 B，可以得到若干字符串 $T$。求所有这些字符串 $T$ 的 $f(T)$ 之和，对 $998244353$ 取模。

输入格式

输入格式如下：

S

$S$ 是一个由 A、B 和 ? 组成的字符串，长度在 $3$ 到 $1000$ 之间（含端点）。

输出格式

输出答案。

A?B?

2

?B?A?B?

15

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

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