B. So You Think You Can Count?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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 ≤ 104), 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 109 + 7.

Examples
Input
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 sl, sl + 1, ..., sr 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.