П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стить рядок 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».

Приклади