#P17573. [JAG 2026 Summer Camp #3] ABbreviation
[JAG 2026 Summer Camp #3] ABbreviation
题目描述
给定一个仅由 A 和 B 组成的字符串 。
你可以对 执行任意次(也可以是零次)以下操作。
- 选择 中一个作为连续子串出现的
AB,将这两个字符替换成一个你选择的大写英文字母(A至Z中的一个)。如果替换后的字母是A或B,那么它可以在后续操作中作为AB的一部分再次参与操作。
例如,当 为 AAB 时,你可以将最后两个字符 AB 替换为 C,得到 AC。如果改为将它们替换为 B,则会得到字符串 AB,你还可以再次对它执行操作。
求对 执行任意次操作后,能够得到多少个不同的字符串。
由于答案可能很大,请输出答案对 取模的结果。
输入格式
输入包含一组测试数据,格式如下。
N
S
第一行包含一个整数 (),表示 的长度。
第二行包含一个长度为 、仅由 A 和 B 组成的字符串 。
输出格式
输出一个整数,表示能够得到的不同字符串的数量对 取模的结果。
4
AABB
104
1
A
1
17
ABBABABAAABBAABBB
894459821