Score : $500$ points

问题描述

在另一个世界中的AtCoder举办了10种类型的竞赛，分别为AAC、...、AJC。从现在开始将会有N场竞赛。 这N场竞赛的类型以字符串S的形式给出：如果S的第i个字符是x，则第i场竞赛为AxC。

AtCoDeer将会从这N场竞赛中选择并参加一场或多场比赛，以满足以下条件：

• 在他所参加的所有比赛序列中，相同类型的竞赛必须是连续的。
  • 形式上，当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取模。 两种选择比赛的方式被认为是不同的，当存在一场竞赛c，使得AtCoDeer在一种方式下参加了c，而在另一种方式下没有参加c。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

AtCoder in another world holds $10$ types of contests called AAC, ..., AJC. There will be $N$ contests from now on.
The types of these $N$ contests are given to you as a string $S$: if the $i$-th character of $S$ is $x$, the $i$-th contest will be A$x$C.
AtCoDeer will choose and participate in one or more contests from the $N$ so that the following condition is satisfied.

• In the sequence of contests he will participate in, the contests of the same type are consecutive.
  • Formally, when AtCoDeer participates in $x$ contests and the $i$-th of them is of type $T_i$, for every triple of integers $(i,j,k)$ such that $1 \le i < j < k \le x$, $T_i=T_j$ must hold if $T_i=T_k$.

Find the number of ways for AtCoDeer to choose contests to participate in, modulo $998244353$.
Two ways to choose contests are considered different when there is a contest $c$ such that AtCoDeer participates in $c$ in one way but not in the other.

Constraints

• $1 \le N \le 1000$
• $|S|=N$
• $S$ consists of uppercase English letters from A through J.

Input

Input is given from Standard Input in the following format:

$N$

$S$

Output

Print the answer as an integer.

Sample Input 1

4
BGBH

Sample Output 1

13

For example, participating in the $1$-st and $3$-rd contests is valid, and so is participating in the $2$-nd and $4$-th contests.
On the other hand, participating in the $1$-st, $2$-nd, $3$-rd, and $4$-th contests is invalid, since the participations in ABCs are not consecutive, violating the condition for the triple $(i,j,k)=(1,2,3)$.
Additionally, it is not allowed to participate in zero contests.
In total, there are $13$ valid ways to participate in some contests.

Sample Input 2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

Sample Output 2

330219020

Be sure to find the count modulo $998244353$.

update @ 2024/3/10 09:33:08