لكل سلسلة نصية $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$.