Para una cadena $T$ formada por A y B, se define $f(T)$ como el número máximo de veces que se puede realizar la siguiente operación.
Operación: Eliminar una aparición de ABA como subsecuencia (no necesariamente contigua) de $T$, y cerrar los huecos resultantes.
Se te da una cadena $S$ formada por A, B y ?. Halla la suma de $f(T)$ sobre todas las cadenas $T$ obtenidas al reemplazar cada ? en $S$ por A o B, módulo $998244353$.
Entrada
La entrada se proporciona en el siguiente formato:
$$S$$
$S$ es una cadena formada por A, B y ?, y su longitud está entre $3$ y $1000$, inclusive.
Salida
Imprime la respuesta.
Ejemplos
Entrada 1
A?B?
Salida 1
2
Entrada 2
?B?A?B?
Salida 2
15
Entrada 3
????????????????????
Salida 3
4595728
Nota
Las posibles cadenas $T$ y sus correspondientes valores de $f(T)$ para el primer ejemplo son los siguientes:
- $T = \texttt{AABA}$: $f(T) = 1$.
- $T = \texttt{AABB}$: $f(T) = 0$.
- $T = \texttt{ABBA}$: $f(T) = 1$.
- $T = \texttt{ABBB}$: $f(T) = 0$.
Por lo tanto, la respuesta es $1 + 0 + 1 + 0 = 2$.