För en sträng $T$ som består av A och B, definiera $f(T)$ som det maximala antalet gånger följande operation kan utföras.
Operation: Ta bort ABA som förekommer som en (inte nödvändigtvis sammanhängande) delsekvens av $T$, och slut de uppkomna luckorna.
Du får en sträng $S$ som består av A, B och ?. Beräkna summan av $f(T)$ över alla strängar $T$ som erhålls genom att ersätta varje ? i $S$ med antingen A eller B, modulo $998244353$.
Indata
Indata ges i följande format:
$$S$$
$S$ är en sträng som består av A, B och ?, och dess längd är mellan $3$ och $1000$, inklusive.
Utdata
Skriv ut svaret.
Examples
Input 1
A?B?
Output 1
2
Input 2
?B?A?B?
Output 2
15
Input 3
????????????????????
Output 3
4595728
Förklaring
De möjliga strängarna $T$ och deras motsvarande värden på $f(T)$ för det första exemplet är följande:
- $T = \texttt{AABA}$: $f(T) = 1$.
- $T = \texttt{AABB}$: $f(T) = 0$.
- $T = \texttt{ABBA}$: $f(T) = 1$.
- $T = \texttt{ABBB}$: $f(T) = 0$.
Därför är svaret $1 + 0 + 1 + 0 = 2$.