Вам дано рядок 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стить рядок s (1 ≤ |s| ≤ 10^5
). Усi його символи — маленькi латинськi букви.
Виведiть цiле число — кiлькiсть гарних непустих пiдпослiдовностей рядка s по модулю 10^9
+ 7(1000000007).
####Примiтка
У першому прикладi є 4 гарнi пiдпослiдовностi: «a», «b», «c», «d».