Problem Description

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

Input Format

The input is given in the following format:

S

$S$ is a string consisting of A, B, and ?, and its length is between $3$ and $1000$, inclusive.

Output Format

Print the answer.

A?B?

2

?B?A?B?

15

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

4595728

Hint

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