现在是 Daskalov 先生的九年级英语课。我们的主角 Deni 对英语很不擅长，于是她在数教室里的苍蝇。这被证明是一项非常无聊的活动，所以她看向了老师在黑板上写的一些文字。她忽略了单词之间的空格，因此整个文本在她看来就是一个长度为 $N$ 的英文字母序列。设该序列中不同字符的数量为 $K$。Deni 开始从这个序列中截取不同的子串，并记下每个字符出现的次数。当这 $K$ 个字母在子串中出现的次数都相等时，她称当前的子串为“神奇的”。
备注：子串是给定字符串中连续书写的一段字符。
在这节英语课上，她能够检查序列中的每一个子串。同时，她统计了有多少个子串是神奇的，最后她对完成这项活动感到非常高兴。Deni 决定她想在每一节英语课上都这样做。但是，随着每一节后续的英语课，Daskalov 先生在黑板上写的文字变得越来越长。所以她向你寻求帮助——你需要编写一个程序，告诉她给定长度为 $N$ 的英文字母序列中有多少个神奇的子串。
任务
编写一个程序 magic，用于计算给定长度为 $N$ 的英文字母序列中神奇子串的数量。位置不同但内容相同的子串被视为不同的子串。
输入格式
从标准输入的第一行，你的程序需要读取一个整数 $N$ —— Daskalov 先生所写序列的字符数。从下一行开始，你的程序需要读取一个长度为 $N$ 的英文字母字符串。字母可以是小写或大写。注意，同一字母的大小写形式被视为不同的字符（例如 $A$ 和 $a$ 是不同的字符）。
输出格式
程序必须将给定字符串中神奇子串的数量打印到标准输出。由于这个数字可能非常大，你需要输出其除以 $1\,000\,000\,007$ 后的余数。
数据范围
- $2 \le N \le 100\,000$
子任务
| 子任务 | 分值 | $N$ | 其他约束 |
|---|---|---|---|
| 1 | 10 | $\le 100$ | 无其他约束。 |
| 2 | 20 | $\le 2000$ | 无其他约束。 |
| 3 | 30 | $\le 100\,000$ | 给定字符串中只有两种字符 ($K=2$)。 |
| 4 | 40 | $\le 100\,000$ | 无其他约束。 |
样例
样例输入 1
8 abccbabc
样例输出 1
4
说明 1
神奇的子串有 abc、cba、abc 和 abccba。注意，例如子串 ab 不是神奇的，因为字母 c 不在其中。
样例输入 2
7 abcABCC
样例输出 2
1
说明 2
只有子串 abcABC 是神奇的（字母 a 和 A 是不同的，因为 a 是小写字母，而 A 是大写字母）。
样例输入 3
20 SwSSSwwwwSwSwwSww wwS
样例输出 3
22
说明 3
神奇子串的数量为 22，其中一个是 SwSwwS。