P6273 [eJOI 2017] Magic

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.

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

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

#### 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](www.ejoi.org) Problem A [Magic](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/magic_statement-en.pdf). Translation provided by: @[```_Wallace_```](https://www.luogu.com.cn/user/61430). Translated by ChatGPT 5