CF756D.Bacterial Melee

Julia is conducting an experiment in her lab. She placed several luminescent bacterial colonies in a horizontal testtube. Different types of bacteria can be distinguished by the color of light they emit. Julia marks types of bacteria with small Latin letters "a", ..., "z".

The testtube is divided into n consecutive regions. Each region is occupied by a single colony of a certain bacteria type at any given moment. Hence, the population of the testtube at any moment can be described by a string of n Latin characters.

Sometimes a colony can decide to conquer another colony in one of the adjacent regions. When that happens, the attacked colony is immediately eliminated and replaced by a colony of the same type as the attacking colony, while the attacking colony keeps its type. Note that a colony can only attack its neighbours within the boundaries of the testtube. At any moment, at most one attack can take place.

For example, consider a testtube with population "babb". There are six options for an attack that may happen next:

• the first colony attacks the second colony (1 → 2), the resulting population is "bbbb";
• 2 → 1, the result is "aabb";
• 2 → 3, the result is "baab";
• 3 → 2, the result is "bbbb" (note that the result is the same as the first option);
• 3 → 4 or 4 → 3, the population does not change.

The pattern of attacks is rather unpredictable. Julia is now wondering how many different configurations of bacteria in the testtube she can obtain after a sequence of attacks takes place (it is possible that no attacks will happen at all). Since this number can be large, find it modulo 109 + 7.

朱莉娅正在她的实验室中进行一项实验。她在一根水平的试管中放置了若干发光细菌菌落。不同种类的细菌可通过其发出光的颜色加以区分。朱莉娅用小写拉丁字母 “a” 到 “z” 标记细菌的种类。

该试管被划分为 $n$ 个连续的区域。在任意时刻，每个区域恰好被一个特定种类的细菌菌落占据。因此，在任意时刻，试管中的种群状态可用一个长度为 $n$ 的拉丁字母字符串来描述。

有时，某个菌落会决定向其相邻区域中的另一个菌落发起进攻。当这种情况发生时，被攻击的菌落将立即被消灭，并被替换为与进攻菌落同种类的新菌落；而进攻菌落自身种类保持不变。注意：菌落只能在其所在试管边界内向其相邻（即左右紧邻）的菌落发起进攻。在任意时刻，至多只允许发生一次进攻。

例如，考虑一个种群状态为 "babb" 的试管。下一步可能发生进攻的情形共有六种：

• 第一个菌落进攻第二个菌落（$1 \to 2$），结果种群变为 "bbbb"；
• $2 \to 1$，结果为 "aabb"；
• $2 \to 3$，结果为 "baab"；
• $3 \to 2$，结果为 "bbbb"（注意：该结果与第一种情形相同）；
• $3 \to 4$ 或 $4 \to 3$，种群状态不发生变化。

进攻发生的模式相当不可预测。朱莉娅现在想知道：经过一系列（可能为零次）进攻后，试管中可能达到多少种不同的细菌配置？由于该数目可能很大，请输出其对 $10^9 + 7$ 取模的结果。

The first line contains an integer n — the number of regions in the testtube (1 ≤ n ≤ 5 000).

The second line contains n small Latin letters that describe the initial population of the testtube.

第一行包含一个整数 $n$ —— 试管中区域的数量（$1 \leq n \leq 5\,000$）。

第二行包含 $n$ 个小写拉丁字母，用于描述试管的初始种群。

Print one number — the answer to the problem modulo 109 + 7.

输出一个数字——该问题答案对 $10^9 + 7$ 取模的结果。

In the first sample the population can never change since all bacteria are of the same type.

In the second sample three configurations are possible: "ab" (no attacks), "aa" (the first colony conquers the second colony), and "bb" (the second colony conquers the first colony).

To get the answer for the third sample, note that more than one attack can happen.

在第一个样例中，种群永远无法发生变化，因为所有细菌都属于同一类型。

在第二个样例中，存在三种可能的构型：“ab”（无攻击发生）、“aa”（第一个菌落征服第二个菌落）以及“bb”（第二个菌落征服第一个菌落）。

要得到第三个样例的答案，请注意：可能发生多次攻击。