Đối với một xâu $T$ gồm các ký tự A và B, định nghĩa $f(T)$ là số lần tối đa có thể thực hiện thao tác sau.

Thao tác: Xóa một xâu ABA xuất hiện dưới dạng một dãy con (không nhất thiết liên tiếp) của $T$, rồi ghép các phần còn lại lại với nhau.

Bạn được cho một xâu $S$ gồm các ký tự A, B và ?. Hãy tìm tổng của $f(T)$ trên tất cả các xâu $T$ thu được bằng cách thay thế mỗi ký tự ? trong $S$ bằng A hoặc B, chia lấy dư cho $998244353$.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

$$S$$

$S$ là một xâu gồm các ký tự A, B và ?, có độ dài từ $3$ đến $1000$ (bao gồm cả hai đầu mút).

Dữ liệu ra

In ra kết quả.

Ví dụ

Dữ liệu vào 1

A?B?

Dữ liệu ra 1

2

Dữ liệu vào 2

?B?A?B?

Dữ liệu ra 2

15

Dữ liệu vào 3

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

Dữ liệu ra 3

4595728

Ghi chú

Các xâu $T$ có thể có và giá trị $f(T)$ tương ứng trong ví dụ đầu tiên như sau:

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

Do đó, đáp án là $1 + 0 + 1 + 0 = 2$.