33OJ
登录 注册

#P17573. [JAG 2026 Summer Camp #3] ABbreviation

[JAG 2026 Summer Camp #3] ABbreviation

Problem Description

You are given a string SS consisting of A and B.

You may perform the following operation on SS any number of times, possibly zero.

  • Choose an occurrence of AB as a contiguous substring of SS, and replace these two characters with a single uppercase English letter (one of A through Z) of your choice. If the replacement letter is A or B, it may be used as part of AB in a later operation.

For example, if SS is AAB, you may replace the last two characters AB with C, resulting in AC. If you replace them with B instead, the resulting string is AB, on which you may perform the operation again.

Find the number of distinct strings that can be obtained from SS by performing the operation any number of times.

Since the answer may be large, print it modulo 998244353998244353.

Input Format

The input consists of a single test case of the following format.

N
S

The first line contains an integer NN (1≤N≤1061\le N\le10^6), representing the length of SS.

The second line contains a string SS of length NN consisting of A and B.

Output Format

Print a single integer representing the number of distinct strings that can be obtained, modulo 998244353998244353.

4
AABB
104
1
A
1
17
ABBABABAAABBAABBB
894459821