A - Colorful Subsequence

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

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

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

制約

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

入力

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

N
S

出力

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


入力例 1

4
abcd

出力例 1

15

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


入力例 2

3
baa

出力例 2

5

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


入力例 3

5
abcab

出力例 3

17

Score : 200 points

Problem Statement

You are given a string S of length N. Among its subsequences, count the ones such that all characters are different, modulo 10^9+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.

Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.

Constraints

  • 1 \leq N \leq 100000
  • S consists of lowercase English letters.
  • |S|=N

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of the subsequences such that all characters are different, modulo 10^9+7.


Sample Input 1

4
abcd

Sample Output 1

15

Since all characters in S itself are different, all its subsequences satisfy the condition.


Sample Input 2

3
baa

Sample Output 2

5

The answer is five: b, two occurrences of a, two occurrences of ba. Note that we do not count baa, since it contains two as.


Sample Input 3

5
abcab

Sample Output 3

17