Подпоследовательности подпоследовательностей

Очень простая

Ограничение по времени выполнения 0,1 секунды

Ограничение по использованию памяти 64 мегабайта

Вам дана строка s, состоящая из строчных латинских букв. Ваша задача — определить количество хороших непустых подпоследовательностей этой строки.

Подпоследовательность считается хорошей, если все её непустые подпоследовательности являются палиндромами.

Две подпоследовательности считаются различными, если они получены удалением символов с разными индексами. То есть, даже если строки подпоследовательностей совпадают, но индексы удалённых символов различаются, такие подпоследовательности считаются разными.

Формат входных данных

Первая строка содержит строку s (1 ≤ |s| ≤ 10^5). Все символы строки — строчные латинские буквы.

Формат выходных данных

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

Примеры

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Примечание

В первом примере существует 4 хорошие подпоследовательности: «a», «b», «c», «d».

Отправки 70

Коэффициент принятия 39 %