Криптограф анализирует зашифрованную строку и считает все скрытые палиндромные подпоследовательности.

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

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

Так как ответ может быть очень большим, выведите его по модулю 1000000007.

Входные данные

В единственной строке задана непустая строка из строчных латинских букв.

Выходные данные

Выведите количество непустых палиндромных подпоследовательностей данной строки по модулю 1000000007.

Ограничения

• 1 <= |s| <= 1000
• строка состоит только из строчных латинских букв 'a'–'z'

Примеры

Пример 1

Входные данные

a

Выходные данные

1

Пример 2

Входные данные

ab

Выходные данные

2

Пример 3

Входные данные

aaa

Выходные данные

7

Пояснение: палиндромы — три одиночных a, три aa и одно aaa, всего 7.