עבור מחרוזת $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$.