E - Chain Contestant Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

別世界の AtCoder では現在、 AAC, ..., AJC の 10 種類のコンテストが開催されており、これから N 回のコンテストが開催されます。
各コンテストの種類は文字列 S として与えられ、 S の i 文字目が x なら i 回目には AxC が開催されます。
シカの 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

出力

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

入力例 1

4
BGBH

出力例 1

13

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

入力例 2

100
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBIEIJEIJIJCGCCFGIEBIHFCGFBFAEJIEJAJJHHEBBBJJJGJJJCCCBAAADCEHIIFEHHBGF

出力例 2

330219020

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

Score : 500 points

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 AxC.
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.