Pour une chaîne de caractères $T$ composée de A et de B, on définit $f(T)$ comme le nombre maximum de fois que l'opération suivante peut être effectuée.

Opération : Supprimer une occurrence de ABA qui apparaît comme une sous-séquence (pas nécessairement contiguë) de $T$, et refermer les espaces résultants.

On vous donne une chaîne de caractères $S$ composée de A, B et ?. Trouvez la somme de $f(T)$ sur toutes les chaînes $T$ obtenues en remplaçant chaque ? dans $S$ par A ou B, modulo $998244353$.

Entrée

L'entrée est donnée dans le format suivant :

$$S$$

$S$ est une chaîne de caractères composée de A, B et ?, et sa longueur est comprise entre $3$ et $1000$ inclus.

Sortie

Affichez la réponse.

Exemples

Entrée 1

A?B?

Sortie 1

2

Entrée 2

?B?A?B?

Sortie 2

15

Entrée 3

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

Sortie 3

4595728

Remarque

Les chaînes $T$ possibles et leurs valeurs correspondantes de $f(T)$ pour le premier exemple sont les suivantes :

• $T = \texttt{AABA}$: $f(T) = 1$.
• $T = \texttt{AABB}$: $f(T) = 0$.
• $T = \texttt{ABBA}$: $f(T) = 1$.
• $T = \texttt{ABBB}$: $f(T) = 0$.

Par conséquent, la réponse est $1 + 0 + 1 + 0 = 2$.