A와 B로 이루어진 문자열 $T$에 대해, 다음 연산을 수행할 수 있는 최대 횟수를 $f(T)$라고 정의합니다.

연산: $T$의 (연속일 필요는 없는) 부분 수열로 나타나는 ABA를 제거하고, 생긴 빈자리를 이어 붙입니다.

A, B, ?로 이루어진 문자열 $S$가 주어집니다. $S$의 각 ?를 A 또는 B로 바꾸어 얻을 수 있는 모든 문자열 $T$에 대한 $f(T)$의 합을 $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$입니다.