Fyrir streng $T$ sem samanstendur af A og B, skilgreinum við $f(T)$ sem mesta fjölda skipta sem hægt er að framkvæma eftirfarandi aðgerð.

Aðgerð: Fjarlægðu ABA sem kemur fyrir sem (ekki endilega samfelld) hlutruna í $T$, og lokaðu eyðunum sem myndast.

Gefinn er strengur $S$ sem samanstendur af A, B og ?. Finndu summu $f(T)$ yfir alla strengi $T$ sem fást með því að skipta hverju ? í $S$ út fyrir annaðhvort A eða B, módúló $998244353$.

Inntak

Inntakið er gefið á eftirfarandi sniði:

$$S$$

$S$ er strengur sem samanstendur af A, B og ?, og lengd hans er á bilinu $3$ til $1000$, hvoru tveggja meðtöldu.

Úttak

Prentið svarið.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 3

4595728

Athugasemd

Mögulegir strengir $T$ og samsvarandi gildi þeirra á $f(T)$ fyrir fyrsta dæmið eru sem hér segir:

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

Því er svarið $1 + 0 + 1 + 0 = 2$.