连续参赛

题目描述

异世界的 AtCoder 举办 10 种类型的比赛，称为 AAC、……、AJC。今后将举办 $N$ 场比赛。

这 $N$ 场比赛的类型以字符串 $S$ 给出：如果 $S$ 的第 $i$ 个字符是 $x$，那么第 $i$ 场比赛是 A$x$C。

AtCoDeer 将从这 $N$ 场比赛中选出 1 场以上参赛，使得以下条件成立：

在他参加的比赛序列中，同类型的比赛连续出现。

形式化地说，设 AtCoDeer 参加 $x$ 场比赛，其中第 $i$ 场的类型为 $T_i$，则对于满足 $1 \le i \lt j \lt k \le x$ 的所有三元组 $(i,j,k)$，若 $T_i=T_k$，则必须满足 $T_i=T_j$。

求 AtCoDeer 选择参赛比赛的方式数，对 $998244353$ 取模。

两种选择方式视为不同，当且仅当存在一场比赛 $c$，使得一种方式中参加 $c$ 而另一种方式中不参加。

输入格式

输入按以下格式从标准输入给出：

$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$ 取模。

数据范围

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