Problem Description

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

A substring of a string is any consecutive segment of that string.

A magic substring is defined as a non-empty substring of $S$ that satisfies: the number of distinct characters in this substring is $k$, and the number of occurrences of each character is the same.

You need to find the number of different magic substrings of the given string $S$.

If two substrings have different left or right endpoints, then they are considered different.

Input Format

The first line: an integer $n$, the length of the string.

The second line: a string $S$.

Output Format

Output one integer, the value of the answer $\bmod (10^9+7)$.

8
abccbabc

4

7
abcABCC

1

20
SwSSSwwwwSwSwwSwwwwS

22

Hint

Sample Explanation

Sample 1 Explanation

• The substrings that satisfy the condition 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}$.

Constraints

This problem uses bundled testdata, with 4 subtasks in total.

• 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. there are only two kinds of characters in $S$).
• Subtask 4 (40 points): no other limits.

For all testdata, 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

The original problem is from: eJOI 2017 Problem A Magic.

Translation provided by: @_Wallace_.

Translated by ChatGPT 5