Дана строка s, найдите число способов разбить s на подстроки так, что если в разбиении содержится k подстрок (p1, p2, p3, ..., pk), то pi = pk - i + 1 для всех i (1 ≤ i ≤ k) и k чётно.
Так как число таких разбиений может быть велико, выведите ответ по модулю 109 + 7.
Выходные данные
Выведите одно целое число — количество требуемых разбиений по модулю 109 + 7.
Примечание
В первом тестовом примере единственным корректным разбиением является ab|cd|cd|ab.
Во втором тестовом примере корректными разбиениями являются ab|b|ab|ab|ab|ab|b|ab, ab|b|abab|abab|b|ab и abbab|ab|ab|abbab.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abcdcdab
|
1
|
|
2
|
abbababababbab
|
3
|