สำหรับสตริง $T$ ที่ประกอบด้วย A และ B ให้นิยาม $f(T)$ เป็นจำนวนครั้งมากที่สุดที่สามารถดำเนินการต่อไปนี้ได้

การดำเนินการ: ลบ ABA ที่ปรากฏเป็นลำดับย่อย (ไม่จำเป็นต้องติดกัน) ของ $T$ ออก แล้วเลื่อนตัวอักษรที่เหลือเข้ามาชิดกัน

กำหนดสตริง $S$ ที่ประกอบด้วย A, B และ ? จงหาผลรวมของ $f(T)$ สำหรับสตริง $T$ ทั้งหมดที่ได้จากการแทนที่ ? แต่ละตัวใน $S$ ด้วย A หรือ B เอาเศษจากการหารด้วย $998244353$

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะกำหนดให้ในรูปแบบต่อไปนี้:

$$S$$

$S$ เป็นสตริงที่ประกอบด้วย A, B และ ? และมีความยาวอยู่ระหว่าง $3$ ถึง $1000$ (รวมขอบเขต)

ข้อมูลส่งออก

พิมพ์คำตอบ

ตัวอย่าง

ข้อมูลนำเข้า 1

A?B?

ข้อมูลส่งออก 1

2

ข้อมูลนำเข้า 2

?B?A?B?

ข้อมูลส่งออก 2

15

ข้อมูลนำเข้า 3

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

ข้อมูลส่งออก 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$