33OJ
登录 注册

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

[JAG 2026 Summer Camp #3] ABbreviation

题目描述

给定一个仅由 A 和 B 组成的字符串 SS。

你可以对 SS 执行任意次(也可以是零次)以下操作。

  • 选择 SS 中一个作为连续子串出现的 AB,将这两个字符替换成一个你选择的大写英文字母(A 至 Z 中的一个)。如果替换后的字母是 A 或 B,那么它可以在后续操作中作为 AB 的一部分再次参与操作。

例如,当 SS 为 AAB 时,你可以将最后两个字符 AB 替换为 C,得到 AC。如果改为将它们替换为 B,则会得到字符串 AB,你还可以再次对它执行操作。

求对 SS 执行任意次操作后,能够得到多少个不同的字符串。

由于答案可能很大,请输出答案对 998244353998244353 取模的结果。

输入格式

输入包含一组测试数据,格式如下。

N
S

第一行包含一个整数 NN(1≤N≤1061\le N\le10^6),表示 SS 的长度。

第二行包含一个长度为 NN、仅由 A 和 B 组成的字符串 SS。

输出格式

输出一个整数,表示能够得到的不同字符串的数量对 998244353998244353 取模的结果。

4
AABB
104
1
A
1
17
ABBABABAAABBAABBB
894459821