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

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

Вам задано рядок $S$, що складається із символів A, B та ?. Знайдіть суму $f(T)$ за всіма рядками $T$, які можна отримати, замінивши кожен символ ? у $S$ на A або B, за модулем $998244353$.

Вхідні дані

Вхідні дані подано в такому форматі:

$$S$$

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

Вихідні дані

Виведіть відповідь.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 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$.