← 返回题目列表

Codeforces · 756/D

D. 细菌混战

中文机器翻译题面 查看原题

朱莉娅正在她的实验室进行一项实验。她将几个发光细菌菌落放入水平试管中。不同类型的细菌可以通过它们发出的光的颜色来区分。朱莉娅用小拉丁字母“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”(第二个殖民地征服第一个殖民地)。

要获得第三个示例的答案,请注意可能会发生不止一次攻击。