配点 : $200$ 点

問題文

長さ $N$ の文字列 $S$ が与えられます。 $S$ の部分列であって、すべて異なる文字からなるものの数を $10^9+7$ で割った余りを答えてください。文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。

ただし、文字列の部分列とは、文字列から文字をいくつか 正の個数 取り出し、もとの文字列から順序を変えずにつなげたものを指します。

制約

• $1 \leq N \leq 100000$
• $S$ は英小文字からなる
• $|S|=N$

入力

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

$N$

$S$

出力

異なる文字からなる部分列の個数を $10^9+7$ で割った余りを出力せよ。

4
abcd

15

$S$ 自体がすべて異なる文字からなるので、すべての部分列が条件を満たします。

3
baa

5

b, a ($2$ 通り), ba ($2$ 通り) の合計 $5$ 通りが答えとなります。baa などはaが $2$ 回現れるため当てはまらないことに注意してください。

5
abcab

17