A және B таңбаларынан тұратын $T$ жолы үшін $f(T)$ мәнін келесі амалды орындауға болатын ең көп рет саны ретінде анықтайық.

Амал: $T$ жолының (міндетті түрде іргелес емес) ішкі тізбегі ретінде кездесетін ABA жолын өшіріп, пайда болған бос орындарды біріктіріңіз.

Сізге A, B және ? таңбаларынан тұратын $S$ жолы берілген. $S$ жолындағы әрбір ? таңбасын A немесе B таңбасымен алмастыру арқылы алынған барлық $T$ жолдары бойынша $f(T)$ мәндерінің қосындысын $998244353$ модулі бойынша табыңыз.

Кіріс деректері

Кіріс деректері келесі форматта беріледі:

$$S$$

$S$ — A, B және ? таңбаларынан тұратын жол, оның ұзындығы $3$ пен $1000$ аралығында (шеткі мәндерді қоса алғанда).

Шығыс деректері

Жауапты шығарыңыз.

Examples

Input 1

A?B?

Output 1

2

Input 2

?B?A?B?

Output 2

15

Input 3

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

Output 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$ болады.