eolymp
bolt
Try our new interface for solving problems

Magic

Time limit 1 second
Memory limit 256 MiB

Now is the English lesson in grade 9 with Mr. Daskalov. Our main character — Deni — is very weak in English and she counts the number of flies in the room. This proves to be very boring activity, so she looks at the board where the teacher has written some text. She ignores the spaces between the words so the whole text seems to her as one big sequence of English letters with length n. Let us denote the number of different characters in this sequence with k. Deni starts to take up different substrings from this sequence and she writes down the number of times each character occurs. When for all of the k letters these numbers are equal, she calls the current substring magical.

Remark. A substring is a part of a given string, which contains consecutively written characters.

During this English lesson she is able to check every substring of the sequence. Meanwhile she has counted how many of the substrings are magical and in the end she is very happy with the accomplished activity. Deni decides that she would like to do so in every English lesson. But with every subsequent English lesson the text on the board written by Mr. Daskalov is becoming longer and longer. So she asks for your help — you have to write a program which tells her the number of magical substrings in a given sequence of n English letters.

Write a program which counts the number of magical substrings in a given sequence of n English letters. Substrings which are the same but on different positions are counted as different

Input data

From the first line of the standard input, your program has to read one integer n~(2 \le n \le 10^5) — the number of characters in the sequence written by Mr. Daskalov. From the next line your program has to read a string of n English letters. The letters can be lower- and uppercase. Note that the lower- and uppercase forms of the same letter are considered to be different characters (A and a are different characters).

Output data

The program must print to the standard output the number of magical substrings in the given string. Since this number may be quite large, you are required to print its remainder when divided by 10^9 + 7.

Examples

Explanation for the first test. The magical substrings are abc, cba, abc and abccba. Note that for example the substring ab is not magical because the letter c is not in it.

Explanation for the second test. Only the substring abcABC is magical (the letters a and A are different because **a** is a lowercase letter and A is an uppercase letter).

Explanation for the third test. The number of magical substrings is 22 and one of them is SwSwwS.

Input example #1
8
abccbabc
Output example #1
4
Input example #2
7
abcABCC
Output example #2
1
Input example #3
20
SwSSSwwwwSwSwwSwwwwS
Output example #3
22
Source EJOI 2017 Day 1 (First European Junior Olympiad in Informatics)