题目描述

题目译自 eJOI2017 Problem A. Magic

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

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

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

任务

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

输入格式

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

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

输出格式

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

8
abccbabc

4

7
abcABCC

1

20
SwSSSwwwwSwSwwSwwwwS

22

数据范围与提示

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

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