朱莉娅正在她的实验室进行一项实验。她将几个发光细菌菌落放入水平试管中。不同类型的细菌可以通过它们发出的光的颜色来区分。朱莉娅用小拉丁字母“a”、...、“z”来标记细菌类型。
试管被分为n个连续的区域。在任何给定时刻,每个区域都被某种细菌类型的单个菌落占据。因此,任意时刻试管的数量可以用一串n个拉丁字符来描述。
有时,一个殖民地可以决定征服邻近地区之一的另一个殖民地。当这种情况发生时,被攻击的群体会立即被消灭,并被与攻击群体相同类型的群体所取代,而攻击群体则保持其类型。请注意,菌落只能攻击试管边界内的邻居。任何时刻,最多只能发生一次攻击。
例如,考虑一个人口为“babb”的试管。接下来可能发生的攻击有六种选择:
- 第一个殖民地攻击第二个殖民地(1 → 2),得到的种群为“bbbb”;
- 2 → 1,结果为“aabb”;
- 2 → 3,结果为“baab”;
- 3 → 2,结果为“bbbb”(注意结果与第一个选项相同);
- 3 → 4或4 → 3,人口没有变化。
攻击的模式相当难以预测。朱莉娅现在想知道在发生一系列攻击后,她可以在试管中获得多少种不同配置的细菌(有可能根本不会发生攻击)。由于该数字可能很大,因此请对 109 + 7 求模。
输入
第一行包含一个整数 n — 试管中的区域数量 (1 ≤ n ≤ 5 000)。
第二行包含 n 个小拉丁字母,描述试管的初始群体。
输出
打印一个数字——以 109 + 7 为模的问题的答案。
示例
输入 #1
3 aaa
输出 #1
1
输入 #2
2 ab
输出 #2
3
输入 #3
4 babb
输出 #3
11
输入#4
7 abacaba
输出#4
589
注意
在第一个样本中,种群永远不会改变,因为所有细菌都属于同一类型。
在第二个示例中,可能存在三种配置:“ab”(无攻击)、“aa”(第一个殖民地征服第二个殖民地)和“bb”(第二个殖民地征服第一个殖民地)。
要获得第三个示例的答案,请注意可能会发生不止一次攻击。