Für eine Zeichenkette $T$, die aus A und B besteht, sei $f(T)$ definiert als die maximale Anzahl von Malen, die die folgende Operation ausgeführt werden kann.

Operation: Entferne ABA, das als (nicht notwendigerweise zusammenhängende) Teilfolge von $T$ auftritt, und schließe die entstehenden Lücken.

Gegeben ist eine Zeichenkette $S$, die aus A, B und ? besteht. Bestimme die Summe von $f(T)$ über alle Zeichenketten $T$, die entstehen, indem jedes ? in $S$ entweder durch A oder durch B ersetzt wird, modulo $998244353$.

Eingabe

Die Eingabe erfolgt im folgenden Format:

$$S$$

$S$ ist eine Zeichenkette, die aus A, B und ? besteht, und ihre Länge liegt zwischen $3$ und $1000$ (einschließlich).

Ausgabe

Gib die Antwort aus.

Beispiele

Eingabe 1

A?B?

Ausgabe 1

2

Eingabe 2

?B?A?B?

Ausgabe 2

15

Eingabe 3

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

Ausgabe 3

4595728

Hinweis

Die möglichen Zeichenketten $T$ und ihre zugehörigen Werte von $f(T)$ für das erste Beispiel lauten wie folgt:

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

Daher lautet die Antwort $1 + 0 + 1 + 0 = 2$.