Per una stringa $T$ composta da A e B, definiamo $f(T)$ come il numero massimo di volte in cui è possibile eseguire la seguente operazione.

Operazione: Rimuovere ABA che appare come sottosequenza (non necessariamente contigua) di $T$, e chiudere gli spazi vuoti risultanti.

Ti viene data una stringa $S$ composta da A, B e ?. Trova la somma di $f(T)$ su tutte le stringhe $T$ ottenute sostituendo ciascun ? in $S$ con A oppure B, modulo $998244353$.

Input

L'input è fornito nel seguente formato:

$$S$$

$S$ è una stringa composta da A, B e ?, e la sua lunghezza è compresa tra $3$ e $1000$, estremi inclusi.

Output

Stampa la risposta.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 3

4595728

Nota

Le possibili stringhe $T$ e i rispettivi valori di $f(T)$ per il primo esempio sono i seguenti:

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

Pertanto, la risposta è $1 + 0 + 1 + 0 = 2$.