Dla napisu $T$ składającego się ze znaków A oraz B, zdefiniujmy $f(T)$ jako maksymalną liczbę razy, jaką można wykonać następującą operację.

Operacja: Usuń ABA, które występuje jako (niekoniecznie spójny) podciąg napisu $T$, i złącz pozostałe znaki, likwidując powstałe luki.

Dany jest napis $S$ składający się ze znaków A, B oraz ?. Znajdź sumę wartości $f(T)$ po wszystkich napisach $T$ otrzymanych poprzez zastąpienie każdego znaku ? w $S$ znakiem A lub B, modulo $998244353$.

Wejście

Wejście podane jest w następującym formacie:

$$S$$

$S$ jest napisem składającym się ze znaków A, B oraz ?, a jego długość wynosi od $3$ do $1000$ włącznie.

Wyjście

Wypisz odpowiedź.

Przykład

Wejście 1

A?B?

Wyjście 1

2

Wejście 2

?B?A?B?

Wyjście 2

15

Wejście 3

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

Wyjście 3

4595728

Uwagi

Możliwe napisy $T$ oraz odpowiadające im wartości $f(T)$ dla pierwszego przykładu są następujące:

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

Zatem odpowiedź wynosi $1 + 0 + 1 + 0 = 2$.