For en streng $T$ som består av A og B, definerer vi $f(T)$ som det maksimale antallet ganger følgende operasjon kan utføres.
Operasjon: Fjern ABA som forekommer som en (ikke nødvendigvis sammenhengende) delsekvens av $T$, og lukk hullene som oppstår.
Du får gitt en streng $S$ som består av A, B og ?. Finn summen av $f(T)$ over alle strenger $T$ som oppnås ved å erstatte hvert ? i $S$ med enten A eller B, modulo $998244353$.
Inndata
Inndataene er gitt i følgende format:
$$S$$
$S$ er en streng som består av A, B og ?, og lengden er mellom $3$ og $1000$, inkludert.
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
Forklaring
De mulige strengene $T$ og deres tilhørende verdier av $f(T)$ for det første eksempelet er som følger:
- $T = \texttt{AABA}$: $f(T) = 1$.
- $T = \texttt{AABB}$: $f(T) = 0$.
- $T = \texttt{ABBA}$: $f(T) = 1$.
- $T = \texttt{ABBB}$: $f(T) = 0$.
Derfor er svaret $1 + 0 + 1 + 0 = 2$.