eolymp
bolt
Try our new interface for solving problems
Məsələlər

Пiдпослiдовностi пiдпослiдовностей

Пiдпослiдовностi пiдпослiдовностей

Zaman məhdudiyyəti 0.1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Giriş verilənləri

Перший рядок мiстить рядок s (1 ≤ |s| ≤ 10^5). Усi його символи — маленькi латинськi букви.

Çıxış verilənləri

Виведiть цiле число — кiлькiсть гарних непустих пiдпослiдовностей рядка s по модулю 10^9 + 7(1000000007).

####Примiтка

У першому прикладi є 4 гарнi пiдпослiдовностi: «a», «b», «c», «d».

Nümunə

Giriş verilənləri #1
abcd
Çıxış verilənləri #1
4
Giriş verilənləri #2
abacaba
Çıxış verilənləri #2
19
Mənbə 2019-2020 ACM-ICPC, SEERC, 1/4 фiналу, Днiпро, Київ, Львiв, Миколаїв, Тернопiль, Харкiв, 14 вересня 2019