Colorful Subsequence

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.

Examples

Input

4 abcd

Output

15

Input

3 baa

Output

5

Input

5 abcab

Output

17

inputFormat

Input

Input is given from Standard Input in the following format:

N S

outputFormat

Output

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

Examples

Input

4 abcd

Output

15

Input

3 baa

Output

5

Input

5 abcab

Output

17

样例

3
baa

5