Balance

题意翻译

【题目描述】 一个仅由a,b,c三种字符组成的字符串，可以对其进行如下两种操作： 1. 选择两个相邻字符，将第一个字符替换成第二个。 2. 选择两个相邻字符，将第二个字符替换成第一个。 这样，通过任意多次的操作，可以得到许多不同的串，为了追求字符的平衡， 我们要求a,b,c三种字符在字符串中出现的次数两两之差都不能大于1。 你的任 务是，统计给定字符串通过任意多次的操作，能够得到的不同的平衡串的个数。 【输入格式】 输入文件包含2行。 第一行包含1个正整数n，表示字符串长度。 第二行包含1个长度为n的字符串。 【输出格式】 输出共1行，包含1个正整数，表示能够得到的平衡串的数量。由于答案可 能很大，因此输出时要对51123987取模。

题目描述

Nick likes strings very much, he likes to rotate them, sort them, rearrange characters within a string... Once he wrote a random string of characters a, b, c on a piece of paper and began to perform the following operations: - to take two adjacent characters and replace the second character with the first one, - to take two adjacent characters and replace the first character with the second one To understand these actions better, let's take a look at a string «abc». All of the following strings can be obtained by performing one of the described operations on «abc»: «bbc», «abb», «acc». Let's denote the frequency of a character for each of the characters a, b and c as the number of occurrences of this character in the string. For example, for string «abc»: | $ a $ | = 1, | $ b $ | = 1, | $ c $ | = 1, and for string «bbc»: | $ a $ | = 0, | $ b $ | = 2, | $ c $ | = 1. While performing the described operations, Nick sometimes got balanced strings. Let's say that a string is balanced, if the frequencies of each character differ by at most 1. That is $ -1<=|a|-|b|<=1 $ , $ -1<=|a|-|c|<=1 $ и $ -1<=|b|-|c|<=1 $ . Would you help Nick find the number of different balanced strings that can be obtained by performing the operations described above, perhaps multiple times, on the given string $ s $ . This number should be calculated modulo $ 51123987 $ .

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=150 $ ) — the length of the given string $ s $ . Next line contains the given string $ s $ . The initial string can be balanced as well, in this case it should be counted too. The given string $ s $ consists only of characters a, b and c.

输出格式

Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string $ s $ , modulo $ 51123987 $ .

输入输出样例

输入样例 #1

4
abca

输出样例 #1

7

输入样例 #2

4
abbc

输出样例 #2

3

输入样例 #3

2
ab

输出样例 #3

1

说明

In the first sample it is possible to get $ 51 $ different strings through the described operations, but only $ 7 $ of them are balanced: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». In the second sample: «abbc», «aabc», «abcc». In the third sample there is only one balanced string — «ab» itself.