Magic

It is the grade 9 English lesson with Mr. Daskalov. Deni, our main character, is very weak in English, so she counts the flies in the room. That turns out to be boring too, so she looks at the board where the teacher has written some text. She ignores the spaces between the words, so the whole text looks to her like one long sequence of English letters of length $N$. Let $K$ be the number of different characters in this sequence. Deni starts taking substrings of the sequence and writing down how many times each character occurs in them. When these numbers are equal for all $K$ letters, she calls the substring magical.

A substring is a part of a given string that contains consecutively written characters.

During this lesson she checks every substring of the sequence, counts how many of them are magical, and ends up very happy with the result. Deni decides she wants to do the same in every English lesson. With each lesson the text Mr. Daskalov writes on the board gets longer, so she asks for your help. Write a program that counts the magical substrings of a given sequence of $N$ English letters. Substrings that are equal but sit at different positions count as different.

The first line of the standard input holds one integer $N$, the number of characters in the sequence written by Mr. Daskalov. The next line holds a string of $N$ English letters. The letters can be lowercase and uppercase. The lowercase and uppercase forms of the same letter count as different characters (A and a are different characters).

Print the number of magical substrings of the given string. This number can be quite large, so print its remainder when divided by 1,000,000,007.

• $2 \le N \le 100\,000$

In the first example the magical substrings are abc, cba, abc and abccba. The substring ab, for instance, is not magical because the letter c is missing from it.

In the second example only the substring abcABC is magical. The letters a and A differ because a is lowercase and A is uppercase.

In the third example the answer is 22, and one of the magical substrings is SwSwwS.