Untuk sebuah string $T$ yang terdiri dari A dan B, definisikan $f(T)$ sebagai jumlah maksimum operasi berikut dapat dilakukan.

Operasi: Hapus ABA yang muncul sebagai subsekuens (tidak harus bersebelahan) dari $T$, lalu rapatkan kembali celah yang terbentuk.

Anda diberikan sebuah string $S$ yang terdiri dari A, B, dan ?. Carilah jumlah dari $f(T)$ untuk semua string $T$ yang diperoleh dengan mengganti setiap ? pada $S$ dengan A atau B, modulo $998244353$.

Masukan

Masukan diberikan dalam format berikut:

$$S$$

$S$ adalah string yang terdiri dari A, B, dan ?, serta panjangnya berada di antara $3$ hingga $1000$, inklusif.

Keluaran

Cetak jawabannya.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 3

4595728

Catatan

String $T$ yang mungkin beserta nilai $f(T)$ yang bersesuaian untuk sampel pertama adalah sebagai berikut:

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

Oleh karena itu, jawabannya adalah $1 + 0 + 1 + 0 = 2$.