Коварный Локи напал на Землю, использовав Тессеракт для того, чтобы переместиться из Асгарда. Понимая ценность этого артефакта, он решает защитить его от использования кем-либо, кроме себя. Для этого он решает немного изменить его внутреннюю структуру так, чтобы только он знал, как её можно восстановить.
После внимательного исследования, внимание Локи привлекла цепочка маленьких кубиков внутри Тессеракта. Среди этих кубиков были крайне похожие друг на друга, что идеально подходило для небольшого, но важного для работы изменения Тессеракта. Проявив восхвалённую в легендах коварность, Локи, в надежде на невнимательность людей, решил внести два изменения таких, чтобы после каждого из них, артефакт выглядел бы таким же, как и раньше.
Всего цепочка, которую собирается менять Локи, состоит из \(n\) кубиков. Среди них есть похожие, на чём и собирается сыграть Локи. Он берёт какой-то отрезок кубиков в этой цепочке, вырывает его, разворачивает и вставляет обратно. При этом, он выбирает отрезок таким образом, чтобы внешне цепочка не изменилась. Затем он повторяет то же самое с другим отрезком, который содержал в себе первый, но не совпадал с ним. Очевидно, после этих двух операций цепочка уже не будет совпадать с исходной, и артефакт будет испорчен.
Чтобы оценить вероятность быть уличённым в порче Тессеракта, Локи решил выяснить, сколькими способами он мог выбрать первый отрезок.
Рассмотрим, к примеру, цепочку \(aabaa\), в которой одинаковыми буквами обозначены похожие кубики. Тогда настоящий Тессеракт содержит цепочку \(a_1a_2ba_3a_4\). Локи может, например, проделать следующую последовательность действий: \(a_1a_2ba_3a_4 \to a_2a_1ba_3a_4 \to a_4a_3ba_1a_2\). Внешне ничего не изменилось, однако цепочка уже другая.
Формат входных данных
В первой и единственной строке задана цепочка, состоящая из маленьких латинских букв, длиной не более \(100{\,}000\).
Формат выходных данных
Единственное число — количество различных первых действий Локи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aabaa
|
8
|