Вам дано рядок 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».