← 返回题目列表

Codeforces · 17/C

C. 平衡

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

尼克非常喜欢字符串,他喜欢旋转字符串、排序字符串、重新排列字符串中的字符……有一次,他在一张纸上写下了随机的字符串a、b、c,并开始执行以下操作:

- 获取两个相邻的字符并将第二个字符替换为第一个字符,
- 获取两个相邻的字符并将第一个字符替换为第二个字符

为了更好地理解这些操作,让我们看一下字符串“abc”。通过对《abc》执行上述操作之一可以获得以下所有字符串:《bbc》、《abb》、《acc》。我们将每个字符 a、b 和 c 的字符频率表示为该字符在字符串中出现的次数。例如,对于字符串“abc”:|a| = 1, |b| = 1, |c| = 1,对于字符串 «bbc»: |a| = 0, |b| = 2, |c| = 1。

在执行所描述的操作时,尼克有时会得到平衡的字符串。假设一个字符串是平衡的,如果每个字符的频率最多相差 1。即 - 1 ≤ |a| - |b| ≤ 1, - 1 ≤ |a| -|c| ≤ 1 и - 1 ≤ |b| -|c| ≤ 1。

你能帮助 Nick 找到通过对给定字符串 s 执行上述操作(可能多次)可以获得的不同平衡字符串的数量吗?该数字应以 51123987 为模进行计算。

输入

第一行包含整数 n (1 ≤ n ≤ 150) — 给定字符串 s 的长度。下一行包含给定的字符串 s。初始字符串也可以是平衡的,在这种情况下它也应该被计算在内。给定的字符串 s 仅由字符 a、b 和 c 组成。

输出

输出唯一的数字 — 通过对给定字符串 s 执行所描述的操作(可能是多次)可获得的不同平衡字符串的数量,模 51123987。

示例

输入 #1

4
abca

输出 #1

7

输入 #2

4
abbc

输出 #2

3

输入 #3

2
ab

输出 #3

1

注意

在第一个示例中,通过所描述的操作可以得到 51 个不同的字符串,但其中只有 7 个是平衡的:《abca》、《bbca》、《bcca》、《bcaa》、《abcc》、《abbc》、《aabc》。在第二个示例中:“abbc”、“aabc”、“abcc”。在第三个示例中,只有一个平衡字符串 — «ab» 本身。