У Farmer John есть секретное сообщение, которое он хочет скрыть от коров: строка длиной не менее 2, содержащая только символы A..Z.
Для шифрования FJ применяет последовательность «операций». Операция над строкой $S$ сначала укорачивает её, удаляя первый или последний символ, затем исходная строка $S$ приписывается в начало или конец. Например, одна операция над ABCD может дать четыре строки:
BCDABCD ABCABCD ABCDABC ABCDBCD
По конечной зашифрованной строке посчитайте, сколькими способами FJ мог получить её, применив одну или несколько последовательных операций к некоторой исходной строке. Операции считаются различными, даже если дают одинаковый результат шифрования. Например, получить AAA из AA можно четырьмя различными способами, соответствующими четырём операциям выше.
Входные данные
- Строка $1$: строка длиной не более 100.
Выходные данные
- Строка $1$: количество различных способов получить эту строку одной или несколькими последовательными операциями над некоторой исходной строкой длиной не менее 2. Если способов нет, выведите ноль.
Примеры
Входные данные 1
ABABA
Выходные данные 1
6
Примечание
Различные способы получить ABABA:
- Начать со строки:
ABA -> AB+ABA - Начать со строки:
ABA -> ABA+BA - Начать со строки:
AB -> AB+A -> AB+ABA - Начать со строки:
AB -> AB+A -> ABA+BA - Начать со строки:
BA -> A+BA -> AB+ABA - Начать со строки:
BA -> A+BA -> ABA+BA
Авторы задачи: Brian Dean и Lewin Gan