题目描述

给定一个长度为 $n$ 的字符串 $S$。设 $S$ 中不同的字符数为 $k$ 。

定义字符串的子串为该字符串某一连续段。

而 有魔法的子串 被定义为 $S$ 的某一非空子串，满足该子串中不同的字符数为 $k$ ，且每个字符的出现的次数都相同。

你需要求出给定字符串 $S$ 的不同的 有魔法的子串 的个数。

若两个子串的左右端点不同，则这两个子串不同。

输入格式

第一行：一个整数 $n$ 表示字符串长度。

第二行：一个字符串 $S$ 。

输出格式

一个整数表示答案 $\bmod (10^9+7)$ 的值。

8
abccbabc

4

7
abcABCC

1

20
SwSSSwwwwSwSwwSwwwwS

22

提示

【输入输出样例解释】

样例 1 解释

• 满足条件的子串有： $\texttt{abc},\texttt{cba},\texttt{abc},\texttt{abccba}$

样例 2 解释

• 仅子串 $\texttt{abcABC}$ 为 有魔法的子串（区分大小写，即 $\texttt{a}\ne \texttt{A}$）。

样例 3 解释

• 其中一个是 $\texttt{SwSwwS}$。

【数据规模与约定】

本题采用多测试点捆绑测试，共有 4 个子任务。

• 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$ （即 $S$ 中只有两种字符）。
• Subtask 4（40 points）：无其他限制。

对于所有数据，保证 $2\le n\le 10^5$，字符集为 $ [\texttt{a},\texttt{z}] \cup [\texttt{A},\texttt{Z}]$

【说明】

原题来自：eJOI 2017 Problem A Magic

翻译提供：@_Wallace_