Суффиксный паспортный контроль
Команда Ужляндии в этом году посещает Венецию, где проходит полуфинал мирового чемпионата по программированию. Паспортный контроль в этом городе-государстве проверяет строку s длины N, записанную в биометрическом паспорте, следующим образом:
Для каждой позиции i ∈ [0..N] проверяется, является ли палиндромом строка s[i..N] + rev(s). Здесь s[i..N] — это суффикс строки, начиная с позиции i (включительно), позиции нумеруются с нуля, сам суффикс может быть пустым, rev(s) — это строка s, записанная в обратном порядке, а "+" обозначает конкатенацию двух строк.
Вам нужно определить количество таких позиций, для которых полученная строка является палиндромом.
Входные данные
В единственной строке входного потока содержится строка длиной не более 10^6 символов.
Выходные данные
Выведите одно целое число — ответ на задачу.