Problem Description

Given a string \( S \) of length \( N \) consisting of characters A and B.

You can perform the following operation zero or more times:

• Choose any consecutive pair of characters in \( S \) that is not AB, and remove them. Then, concatenate the remaining (possibly empty) strings on both sides, and let this be the new \( S \).

Find the number of distinct possible strings \( S \) after performing the operations, modulo \( 998244353 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( S \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
BBA

Sample Output #1

3

Sample Input #2

5
ABABA

Sample Output #2

3

Sample Input #3

9
BABBAAAAB

Sample Output #3

14

Sample Input #4

48
AABABBBAABAAABAAABBBAAABBBAABAABBABAABBAAAAABBBB

Sample Output #4

3073910

Notes/Hints

Constraints

• \( 2 \leq N \leq 10^6 \)
• \( S \) is a string of length \( N \) consisting of A and B.

Sample Explanation 1

The possible strings \( S \) after operations are A, B, and BBA, totaling 3 possibilities.

Sample Explanation 2

The possible strings \( S \) after operations are A, ABA, and ABABA, totaling 3 possibilities.

见题面 Input 部分

见题面 Output 部分