You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

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

你需要求出给定字符串 $S$ 的不同的 均衡的子串 的个数。最终结果模$10^9+7$输出。

若两个子串的左右端点不同，则这两个子串不同。注意字母区分大小写。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

8
abccbabc

样例输出 #1

4

样例 #2

样例输入 #2

7
abcABCC

样例输出 #2

1

样例 #3

样例输入 #3

20
SwSSSwwwwSwSwwSwwwwS

样例输出 #3

22

提示

样例1解释：

满足条件的子串有： $abc,cba,abc,abccba$

数据范围

对于所有数据，保证 $2\le n\le 10^5$，字符只包含大写字母和小写字母。

特殊性质：字符串的第奇数位都是相同的字符。