配点 : $500$ 点

問題文

別世界の 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$ に出場するがもう片方の選び方では出場しないということを指します。

制約

• $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$ で割った余りを求めることに注意してください。