尼克非常喜欢字符串,他喜欢旋转字符串、排序字符串、重新排列字符串中的字符……有一次,他在一张纸上写下了随机的字符串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» 本身。