Никита очень любит строки, любит их ворочать, сортировать, что-то менять местами... И вот в очередной раз он написал на листочке случайную строку из символов 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.
Выходные данные
В единственной строке выходных данных выведите количество различных сбалансированных строк, которые могут быть получены из заданной строки s многократным применением описанных операций. Ответ нужно выводить по модулю 51123987.
Примечание
В первом примере с помощью описанных операций можно получить 51 различную строку, но только 7 из них будут сбалансированными: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». Во втором примере: «abbc», «aabc», «abcc». В третьем примере единственная строка, которая будет сбалансированной — это она сама, «ab».