题目描述

题目译自 eJOI2017 Problem A. Magic

现在 Daskalov 老师正在教授 9 年级的英语课。我们的主角——Deni，英语奇差无比，她正在清点房间内苍蝇的数量。事实证明，这是一个无聊透顶的游戏。所以她看向了老师写字的黑板，并且忽略了字母间的空格，所以整段文本在她看来是一个长度为 $N$ 的巨大的字母序列。我们设该序列中共有 $K$ 个不同的字母。Deni 开始从这个序列中取出不同的子串并记录下每个字母出现的次数。当 $K$ 种字母出现的次数都相同时，她认为当前子串是有魔力的。

注：子串是指一个给定的字符串的一部分，其包含连续位置的字母。

在这节英语课上，她得以检查序列中的每一个子串。与此同时，她还计算了有魔力的子串的数量。最后，她对自己完成的活动十分满意。Deni 决定她在每节英语课上都要这么做。但日后的英语课 Daskalov 老师在黑板上写下的文本越来越长了。所以她向你寻求帮助——你必须写一个程序计算出一个长度为 $N$ 的序列中有魔力的子串的数量。

---

任务

编写一个程序，计算在给定的长度为 $N$ 的英文字母序列中有魔力的子串的数量。当两个子串长得一样但位置不同时，视为不同的子串。

---

输入格式

输入第一行一个整数 $N$，表示序列的长度。

第二行输入一个长度为 $N$ 的英文字母序列，字母可以是大写或小写。对于同一个字母的大小写，它们看做不同的字符。

---

输出格式

输出有魔力的字符串的数量对 $10^9+7$ 取模的结果。

---

样例 1

输入

8
abccbabc

输出

4

解释：abc cba abc abccba 都是有魔力的字符串。

注意，ab 不是有魔力的字符串，因为 c 在其中没有出现。

---

样例 2

输入

7
abcABCC

输出

1

解释：仅 abcABC 是（请注意小写 a 和大写 A 是不一样的）。

---

样例 3

输入

20
SwSSSwwwwSwSwwSwwwwS

输出

22

解释：共有 $22$ 个有魔力的字符串。其中一个是 SwSwwS。

---

数据范围与提示

对于 $100\%$ 的数据，$2 \le N \le 10^5$。

详细子任务附加限制及分值如下表所示。

子任务编号	分数	$N$	限制
1	10	$\le 100$	无特殊限制
2	20	$\le 2\times 10^3$
3	30	$\le 10^5$	$K=2$
4	40		无特殊限制