CF756D Bacterial Melee

Julia 在她的实验室里进行了一项实验。她将几个发光细菌菌落放在水平试管中。不同类型的细菌可以通过它们发出的光的颜色区分开来。Julia 用小写拉丁字母 "a" 到 "z" 标记细菌的种类。 试管被分为 $n$ 个连续的区域。每个区域在任意时刻都被一种类型的细菌菌落占据。因此，试管内在任意时刻的菌落分布可以用一个长度为 $n$ 的拉丁字母字符串来描述。 有时，一个菌落可能会决定攻击邻近区域的另一个菌落。如果发生攻击，被攻击的菌落会立即被消灭，并由与攻击菌落相同类型的菌落取而代之，而攻击方的类型保持不变。注意，菌落只能攻击试管边界内的相邻菌落。在任意一个时刻，至多只能进行一次攻击。 例如，考虑菌落分布为 "babb" 的试管，下一步可能发生的六种攻击方式如下： - 第一个菌落攻击第二个菌落（$1\to2$），结果为 "bbbb"； - $2\to1$，结果为 "aabb"； - $2\to3$，结果为 "baab"； - $3\to2$，结果为 "bbbb"（注意与第一种情况结果相同）； - $3\to4$ 或 $4\to3$，菌落分布不会改变。 攻击的模式是不可预测的。Julia 现在想知道，经过一系列攻击后，她最多能获得多少种不同的菌落分布（也允许没有发生任何攻击）。由于结果可能很大，请输出结果对 $10^{9}+7$ 取模。

第一行包含一个整数 $n$，表示试管中的区域数（$1\le n\le 5000$）。 第二行包含 $n$ 个小写拉丁字母，描述了试管最初的菌落分布。

输出一个整数，表示答案对 $10^{9}+7$ 取模之后的值。

在第一个样例中，所有细菌类型相同，因此菌落分布永远不会改变。 在第二个样例中，可以出现三种分布："ab"（没有攻击）、"aa"（第一个菌落征服第二个菌落）、和 "bb"（第二个菌落征服第一个菌落）。 对于第三个样例，需要注意可能发生多次攻击。 由 ChatGPT 5 翻译