← 返回题目列表

AtCoder · abc215_e

H. 连锁参赛者

中文机器翻译题面 查看原题

分数: 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.