Problem Description

Given a string \( S \) of length \( n \). Let \( k \) be the number of distinct characters in \( S \).

A substring is defined as any continuous segment of the string.

A magic substring is defined as a non-empty substring of \( S \) that satisfies the following conditions:
- It contains \( k \) distinct characters.
- Each character appears the same number of times.

You need to find the number of distinct magic substrings in the given string \( S \).

Two substrings are considered different if their left and right endpoints are different.

Input Format

The first line contains an integer \( n \), representing the length of the string.

The second line contains the string \( S \).

Output Format

Output an integer representing the answer modulo \( (10^9 + 7) \).

Sample Input and Output

Sample Input #1

8
abccbabc

Sample Output #1

4

Sample Input #2

7
abcABCC

Sample Output #2

1

Sample Input #3

20
SwSSSwwwwSwSwwSwwwwS

Sample Output #3

22

Notes

Sample Explanation

Sample 1 Explanation

• The substrings that meet the criteria are: \(\texttt{abc}\), \(\texttt{cba}\), \(\texttt{abc}\), \(\texttt{abccba}\).

Sample 2 Explanation

• Only the substring \(\texttt{abcABC}\) is a magic substring (case-sensitive, i.e., \(\texttt{a} \ne \texttt{A}\)).

Sample 3 Explanation

• One of them is \(\texttt{SwSwwS}\).

Data Constraints

This problem uses multiple test cases bundled together, with 4 subtasks.

• Subtask 1 (10 points): \(2 \le n \le 100\).
• Subtask 2 (20 points): \(2 \le n \le 2 \times 10^3\).
• Subtask 3 (30 points): \(2 \le n \le 10^5\), \(k = 2\) (i.e., \(S\) contains only two characters).
• Subtask 4 (40 points): No additional constraints.

For all data, it is guaranteed that \(2 \le n \le 10^5\), and the character set is \([\texttt{a}, \texttt{z}] \cup [\texttt{A}, \texttt{Z}]\).

Notes

Original problem from: eJOI 2017 Problem A Magic

Translation provided by: @_Wallace_

见题面 Input 部分

见题面 Output 部分