Contest Duration: ~ (local time) (160 minutes) Back to Home
A - Colorful Subsequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

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

制約

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

入力

N
S


入力例 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