Для строки $T$, состоящей из символов A и B, определим $f(T)$ как максимальное количество раз, которое можно выполнить следующую операцию.

Операция: удалить ABA, встречающееся как (не обязательно непрерывная) подпоследовательность строки $T$, и сдвинуть оставшиеся символы, закрывая образовавшиеся промежутки.

Дана строка $S$, состоящая из символов A, B и ?. Найдите сумму $f(T)$ по всем строкам $T$, которые можно получить, заменив каждый символ ? в $S$ на A или B, по модулю $998244353$.

Входные данные

Входные данные даны в следующем формате:

$$S$$

$S$ — строка, состоящая из символов A, B и ?, её длина составляет от $3$ до $1000$ включительно.

Выходные данные

Выведите ответ.

Примеры

Входные данные 1

A?B?

Выходные данные 1

2

Входные данные 2

?B?A?B?

Выходные данные 2

15

Входные данные 3

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

Выходные данные 3

4595728

Примечание

Возможные строки $T$ и соответствующие им значения $f(T)$ для первого примера приведены ниже:

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

Следовательно, ответ равен $1 + 0 + 1 + 0 = 2$.