P17551 [JAG 2026 Summer Camp #2] Take Many ABA

For a string $T$ consisting of `A` and `B`, define $f(T)$ as the maximum number of times the following operation can be performed. **Operation:** Remove `ABA` that appears as a (not necessarily contiguous) subsequence of $T$, and close up the resulting gaps. You are given a string $S$ consisting of `A`, `B`, and `?`. Find the sum of $f(T)$ over all strings $T$ obtained by replacing each `?` in $S$ with either `A` or `B`, modulo $998244353$.

The input is given in the following format: ```text S ``` $S$ is a string consisting of `A`, `B`, and `?`, and its length is between $3$ and $1000$, inclusive.

Print the answer.

The possible strings $T$ and their corresponding values of $f(T)$ for the first sample are as follows: - $T=\texttt{AABA}$: $f(T)=1$. - $T=\texttt{AABB}$: $f(T)=0$. - $T=\texttt{ABBA}$: $f(T)=1$. - $T=\texttt{ABBB}$: $f(T)=0$. Therefore, the answer is $1+0+1+0=2$.