Бальф учится играть в игру под названием Бума. В этой игре ему дается ряд цветных шаров. Он должен выбрать цвет одного нового шара и место для его вставки (между двумя шарами, или слева от всех мячей, или справа от всех мячей).
Когда мяч вставляется, повторяется следующее: если какой-то сегмент шаров одного цвета стал длиннее в результате предыдущего действия и его длина стала не менее 3, то все шары этого сегмента удаляются.
Рассмотрим, например, ряд шаров AAABBBWWBB. Предположим, Бальф выбирает шар цвета W и место для его вставки после шестого шара, т.е. слева от двух W. После того, как Бальф вставляет этот шар, шары цвета W удаляются, так как этот сегмент стал длиннее и теперь имеет длину 3, поэтому строка становится AAABBBBB. Шары цвета B теперь удаляются, потому что сегмент шаров цвета B стал длиннее и теперь имеет длину 5. Таким образом, строка становится AAA. Однако сейчас ни один из шаров не удаляется, потому что нет удлиненного сегмента.
Помогите Бальфу посчитать количество возможных способов выбрать цвет нового шара и место для его вставки, которое приведет к удалению всех шаров.
Содержит непустую строку из прописных букв английского алфавита длиной не более 3⋅105. Каждая буква представляет собой шар соответствующего цвета.
Выведите количество способов выбрать цвет и положение нового шара, чтобы уничтожить все шары.