403860: GYM101343 B So You Think You Can Count?

B. So You Think You Can Count?time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Elissa is so clever girl, even though her age is 5 years only. Yesterday she spent all the day learning how to count. Currently she is able to solve many complex counting questions, so she decided to invent a new counting problem in order to help preparing this contest.

Elissa will give you a string s consisting of digits only (from '0' to '9'), and your task is to count in how many ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string.

A beautiful sub-string b is a sub-string from string s, such that b contains unique digits only (i.e. each digit from '0' to '9' can exist at most one time).

Elissa thinks that no one can solve this problem because it is very hard. Can you?

Input

The first line contains an integer n (1 ≤ n ≤ 10⁴), where n is the length of the string s. The second line contains a string s consisting of digits only.

Output

Print the number of ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. Since the number of ways may be too large, print the answer modulo 10⁹ + 7.

ExamplesInput

4
1213

Output

6

Input

5
12345

Output

16

Input

7
5112516

Output

28

Note

A sub-string of the string s is a sequence s_l, s_l + 1, ..., s_r for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.

In the first test case you can divide the given string in 6 ways, which are:

1. 1|2|1|3
2. 1|2|13
3. 1|21|3
4. 1|213
5. 12|1|3
6. 12|13

Note that you cannot divide it to (121|3) because the first sub-string contain the digit '1' twice.