Chain Contestant

题目描述

AtCoder 在异世界举办 10 种比赛，分别称为 AAC, ..., AJC。今后将会有 $N$ 场比赛。
这 $N$ 场比赛的比赛类型用字符串 $S$ 给出：如果 $S$ 的第 $i$ 个字符是 $x$，则第 $i$ 场比赛是 A$x$C。
AtCoDeer 将从这 $N$ 场比赛中选择并参加一场或多场比赛，使得满足以下条件。

在他将要参加的比赛序列中，相同类型的比赛是连续的。 形式上，当 AtCoDeer 参加 $x$ 场比赛且第 $i$ 场的类型为 $T_i$ 时，对于任意满足 1 \le i < j < k \le x 的整数三元组，如果 $T_i=T_k$ 则必须有 $T_i=T_j$。

求 AtCoDeer 选择要参加的比赛的方法数，对 $998244353$ 取模。
当存在一场比赛 $c$，AtCoDeer 在一种选择中参加了 $c$ 而在另一种选择中没有参加 $c$ 时，这两种选择被认为不同。

输入格式

输入以标准输入给出，格式如下： $N$ $S$

输出格式

打印答案（整数）。

4
BGBH

13

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

330219020

提示

$1 \le N \le 1000$ $|S|=N$ $S$ 由从 A 到 J 的大写英文字母组成。例如，参加第 $1$ 场和第 $3$ 场是有效的，参加第 $2$ 场和第 $4$ 场也是有效的。
另一方面，参加第 $1$、$2$、$3$、$4$ 场是无效的，因为 ABC 的参与不是连续的，违反了三元组 $(i,j,k)=(1,2,3)$ 的条件。
另外，不允许不参加任何比赛。
总共有 $13$ 种有效的参加方式。
记得对 $998244353$ 取模。

标签: AtCoder|abc215E

来源

AtCoder|abc215E