Merkkijonolle $T$, joka koostuu merkeistä A ja B, määritellään $f(T)$ suurimmaksi mahdolliseksi määräksi kertoja, jonka seuraava operaatio voidaan suorittaa.

Operaatio: Poista ABA, joka esiintyy merkkijonon $T$ (ei välttämättä yhtenäisenä) alijonona, ja kuro syntyneet aukot umpeen.

Sinulle annetaan merkkijono $S$, joka koostuu merkeistä A, B ja ?. Laske arvojen $f(T)$ summa yli kaikkien merkkijonojen $T$, jotka saadaan korvaamalla jokainen merkkijonon $S$ merkki ? joko merkillä A tai merkillä B, modulo $998244353$.

Syöte

Syöte annetaan seuraavassa muodossa:

$$S$$

$S$ on merkkijono, joka koostuu merkeistä A, B ja ?, ja sen pituus on välillä $3$ ja $1000$, rajat mukaan lukien.

Tuloste

Tulosta vastaus.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 3

4595728

Huomautus

Mahdolliset merkkijonot $T$ ja niitä vastaavat arvot $f(T)$ ensimmäisessä esimerkissä ovat seuraavat:

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

Näin ollen vastaus on $1 + 0 + 1 + 0 = 2$.