E - Chain Contestant

得分：$500$ 分

问题描述

AtCoder in another world 举办了 $10$ 种类型的比赛，分别为 AAC、...、AJC。现在将要举办 $N$ 场比赛。
这 $N$ 场比赛的类型以字符串 $S$ 的形式给出：如果 $S$ 的第 $i$ 个字符是 $x$，则第 $i$ 场比赛的类型为 A$x$C。
AtCoDeer 将选择并参加其中一场或多场比赛，以满足以下条件。

• 他参加的比赛序列中，相同类型的比赛必须连续进行。
  • 具体地，当 AtCoDeer 参加了 $x$ 场比赛且其中第 $i$ 场的类型为 $T_i$ 时，对于所有满足 $1 \le i < j < k \le x$ 的整数三元组 $(i,j,k)$，如果 $T_i=T_k$，则必须满足 $T_i=T_j$。

求 AtCoDeer 选择参加比赛的方案数，结果对 $998244353$ 取模。
只要存在某种方案使 AtCoDeer 在其中的一种方式中参加了比赛 $c$，而在另一种方式中没有参加比赛 $c$，则认为两种方案是不同的。

约束

• $1 \le N \le 1000$
• $|S|=N$
• $S$ 由大写英文字母 A 到 J 构成。

输入

从标准输入读入输入数据，具体格式如下：

$N$

$S$

输出

输出一个整数表示答案。

4
BGBH

13

例如，参加第 $1$ 场和第 $3$ 场比赛是有效的，参加第 $2$ 场和第 $4$ 场比赛也是有效的。
另一方面，参加第 $1$ 场、第 $2$ 场、第 $3$ 场和第 $4$ 场比赛是无效的，因为 ABC 类型的比赛不是连续的，违反了三元组 $(i,j,k)=(1,2,3)$ 的条件。
另外，不允许不参加任何比赛。
总共，有 $13$ 种有效的参赛方案。

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

330219020

请务必对计数取模 $998244353$。