G. Палиндромное разбиение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка s, найдите число способов разбить s на подстроки так, что если в разбиении содержится k подстрок (p1, p2, p3, ..., pk), то pi = pk - i + 1 для всех i (1 ≤ i ≤ k) и k чётно.

Так как число таких разбиений может быть велико, выведите ответ по модулю 109 + 7.

Входные данные

В единственной строке содержится строка s (2 ≤ |s| ≤ 106) чётной длины, состоящая из строчных букв английского алфавита.

Выходные данные

Выведите одно целое число — количество требуемых разбиений по модулю 109 + 7.

Примеры
Входные данные
abcdcdab
Выходные данные
1
Входные данные
abbababababbab
Выходные данные
3
Примечание

В первом тестовом примере единственным корректным разбиением является ab|cd|cd|ab.

Во втором тестовом примере корректными разбиениями являются ab|b|ab|ab|ab|ab|b|ab, ab|b|abab|abab|b|ab и abbab|ab|ab|abbab.