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

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

Print the answer.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 3

4595728

Note

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