题目描述

別世界の AtCoder では現在、 AAC, ..., AJC の $10$ 種類のコンテストが開催されており、これから $N$ 回のコンテストが開催されます。
各コンテストの種類は文字列 $S$ として与えられ、 $S$ の $i$ 文字目が $x$ なら $i$ 回目には A$x$C が開催されます。
シカの AtCoDeer くんは、 $N$ 個のコンテストから $1$ 個以上いくつか選んで、以下の条件を満たすように選んで出場します。

• 出るコンテストを順番を保ったまま抜き出したとき、コンテストの種類ごとにひとかたまりとなっている。
  • 厳密には、 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$ で割った余りを求めてください。
ただし、 $2$ つのコンテストの選び方が異なるとは、あるコンテスト $c$ が存在して、片方の選び方では $c$ に出場するがもう片方の選び方では出場しないということを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$

输出格式

答えを整数として出力せよ。

题目大意

给定一个长度为 $N(1 \le N \le 10^3)$ 的只含有字符 $\texttt{A}$ 到 $\texttt{J}$ 字符串 $S$，你需要寻找出一个字符串子集 $T$ 满足：

• 任意一对 $(i,j,k)(1 \le i < j < k \le N)$ 的三元组，如果 $T_i=T_k$，那么 $T_i=T_j$ 一定成立。

求出子集 $T$ 的方案数，答案对 $998244353$ 取模。

Translated by

4
BGBH

13

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

330219020

提示

制約

• $1\ \le\ N\ \le\ 1000$
• $|S|=N$
• $S$ は A から J までの英大文字のみからなる

Sample Explanation 1

例えば、 $1,3$ 回目のコンテストに出場する、 $2,4$ 回目のコンテストに出場するという選び方は条件を満たします。 一方、 $1,2,3,4$ 回目のコンテストに出場する場合、 ABC への出場がひとかたまりになっておらず、整数組 $(i,j,k)=(1,2,3)$ について条件に違反します。 また、全てのコンテストに出場しないということも認められません。 問題文の条件に適する出場するコンテストの選び方は $13$ 通りあります。

Sample Explanation 2

総数を $998244353$ で割った余りを求めることに注意してください。