#P17573. [JAG 2026 Summer Camp #3] ABbreviation
[JAG 2026 Summer Camp #3] ABbreviation
Problem Description
You are given a string consisting of A and B.
You may perform the following operation on any number of times, possibly zero.
- Choose an occurrence of
ABas a contiguous substring of , and replace these two characters with a single uppercase English letter (one ofAthroughZ) of your choice. If the replacement letter isAorB, it may be used as part ofABin a later operation.
For example, if 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 by performing the operation any number of times.
Since the answer may be large, print it modulo .
Input Format
The input consists of a single test case of the following format.
N
S
The first line contains an integer (), representing the length of .
The second line contains a string of length consisting of A and B.
Output Format
Print a single integer representing the number of distinct strings that can be obtained, modulo .
4
AABB
104
1
A
1
17
ABBABABAAABBAABBB
894459821