시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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.

Remarks: 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 magic 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.

입력

From the first line of the standard input, your program has to read one integer N – 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).

출력

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 1 000 000 007.

제한

  • 2 ≤ N ≤ 100 000

서브태스크 1 (10점)

  • N ≤ 100
  • There are no further constraints.

서브태스크 2 (20점)

  • N ≤ 2,000
  • There are no further constraints.

서브태스크 3 (30점)

  • N ≤ 100,000
  • There are only two kinds of characters in the given string (K=2).

서브태스크 4 (40점)

  • N ≤ 100,000
  • There are no further constraints.

예제 입력 1

8
abccbabc

예제 출력 1

4

예제 입력 2

7
abcABCC

예제 출력 2

1

예제 입력 3

20
SwSSSwwwwSwSwwSwwwwS

예제 출력 3

22

힌트

Explanation of the example 1: 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 of the example 2: 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 of the example 3: The number of magical substrings is 22 and one of them is SwSwwS.

채점

  • 예제는 채점하지 않는다.