分数: 500 点
问题陈述
AtCoder 在另一个世界举行 10 称为 AAC、...、AJC 的比赛类型。会有 N 比赛从现在开始。
这些的类型 N 竞赛以字符串形式提供给您 S:如果 i- 第一个字符 S is x, i第一场比赛将是 AxC.
AtCoDeer 将选择并参加一场或多场比赛 N ,从而满足以下条件。
- 按照他参加的比赛顺序,同类型的比赛是连续的。
- 正式来说,当 AtCoDeer 参与时 x 竞赛和 i- 其中第一个是类型 T_i,对于每个整数三元组 (i,j,k) 这样 1 \le i < j < k \le x, T_i=T_j 必须保持,如果 T_i=T_k.
求AtCoDeer选择参加比赛的方式数量,取模 998244353.
有比赛时两种选择比赛的方式被认为是不同的 c 使得 AtCoDeer 参与 c 以一种方式,但不是以另一种方式。
约束
- 1 \le N \le 1000
- |S|=N
- S 由大写英文字母组成
A通过J.
输入
输入由标准输入按以下格式给出:
N S
输出
将答案打印为整数。
示例输入 1
4 BGBH
示例输出 1
13
例如,参加 1-st 和 3-rd 竞赛有效,参加 2-nd 和 4第 次比赛。
另一方面,参加 1-st, 2-nd, 3-rd,和 4第 次比赛无效,因为参加 ABC 的比赛不连续,违反了三重比赛的条件 (i,j,k)=(1,2,3).
此外,不允许参加零竞赛。
总共有 13 参加某些竞赛的有效方式。
示例输入 2
100 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF
示例输出 2
330219020
一定要找到计数模数 998244353.