萨尔马莱（Sarmale）是由肉和/或米饭（以及其他香料和酱汁）煮熟，并用葡萄叶或酸白菜叶包裹而成的。这是罗马尼亚人在圣诞节期间享用的一道非常美味的佳肴，通常用猪肉制作。当然，每个母亲和祖母都有自己独特的配方，因此萨尔马莱的版本多得超乎想象。

你准备了 26 种不同类型的萨尔马莱，用字母 ‘a’、‘b’、‘c’、……、‘z’ 表示。你将它们排在一个长托盘上。你只知道晚餐至少会有两位客人，但不确定具体有多少人。你想选择托盘上的某个非空子数组（连续子序列）分给客人们（剩下的你自己吃）。你并不真正了解客人们喜欢什么、不喜欢什么，所以你决定，如果有 $k$ 位客人，你就将该子数组分割成 $k$ 个更小的子数组，使得每个子数组中包含的不同类型萨尔马莱的数量相同。

因此，你现在面临以下问题：给定一个由小写英文字母组成的字符串，计算有多少种方法可以选取一个子数组，并将其分割成两个或更多个子数组，使得每个子数组中不同字母的数量相同。确切地说，你需要计算的是分割方案的总数，而不是可以被分割的子数组的数量。

输入格式

第一行包含一个整数 $n$，表示托盘的长度（$2 \le n \le 10^6$）。

第二行包含一个长度为 $n$ 的小写英文字母字符串，按顺序表示托盘上萨尔马莱的类型。

输出格式

输出可能分割方案的总数模 $10^9 + 7$ 的结果。

样例

输入样例 1

3
aaa

输出样例 1

5

输入样例 2

6
aabbaa

输出样例 2

43

输入样例 3

20
aababbababbababhhsse

输出样例 3

7027

说明

在第一个样例中，共有 5 种分割方案：

• 子数组 aa（前两个字符）可以有 1 种方式分割成 2 个子数组。
• 子数组 aa（后两个字符）可以有 1 种方式分割成 2 个子数组。
• 子数组 aaa 可以有 2 种方式分割给 2 位客人（分成 2 个子数组），以及 1 种方式分割给 3 位客人（分成 3 个子数组）。