C. Баланс
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
128 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Никита очень любит строки, любит их ворочать, сортировать, что-то менять местами... И вот в очередной раз он написал на листочке случайную строку из символов a, b, c, и стал делать следующие операции:

  • взять два соседних символа строки и заменить второй символ первым,
  • взять два соседних символа строки и заменить первый символ вторым.

Чтобы лучше понять эти действия, рассмотрим их на примере строки «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.

Помогите Никите посчитать количество различных сбалансированных строк, которые можно получить, применяя многократно вышеуказанные операции к заданной строке s. Это число требуется посчитать по модулю 51123987.

Входные данные

В первой строке входных данных содержится целое число n (1 ≤ n ≤ 150) — длина заданной строки s. Следующая строка содержит s. Строка с самого начала может быть сбалансированной, в этом случае её тоже нужно включить в ответ. Заданная строка s содержит только буквы a, b и c.

Выходные данные

В единственной строке выходных данных выведите количество различных сбалансированных строк, которые могут быть получены из заданной строки s многократным применением описанных операций. Ответ нужно выводить по модулю 51123987.

Примеры
Входные данные
4
abca
Выходные данные
7
Входные данные
4
abbc
Выходные данные
3
Входные данные
2
ab
Выходные данные
1
Примечание

В первом примере с помощью описанных операций можно получить 51 различную строку, но только 7 из них будут сбалансированными: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». Во втором примере: «abbc», «aabc», «abcc». В третьем примере единственная строка, которая будет сбалансированной — это она сама, «ab».