Задачи
J. Пiдпослiдовностi пiдпослiдовностей
J. Пiдпослiдовностi пiдпослiдовностей
Вам дано рядок s з маленьких латинських букв. Ваша задача — знайти кiлькiсть гарних непустих пiдпослiдовностей цього рядка.
Пiдпослiдовнiсть називається гарною, якщо усi її непустi пiдпослiдовностi — палiндроми.
Двi пiдпослiдовностi вважаються рiзними, якщо їх можна отримати видаленням символiв з рiзними iндексами. Тобто, навiть якщо рядки пiдпослiдовностей збiгаються, але iндекси символiв, якi буди видаленi, рiзнi, то цi пiдпослiдовностi вважаються рiзними.
Формат вхiдних даних
Перший рядок мiстить рядок s (**1 ≤ |s| ≤ 105
**). Усi його символи — маленькi латинськi букви.
Формат вихiдних даних
Виведiть цiле число — кiлькiсть гарних непустих пiдпослiдовностей рядка s по модулю 109
+ 7
(1000000007).
Примiтка
У першому прикладi є 4 гарнi пiдпослiдовностi: «a», «b», «c», «d».
Входные данные #1
abcd
Выходные данные #1
4
Входные данные #2
abacaba
Выходные данные #2
19