D. Палиндромные пары
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Дана непустая строка s, состоящая из строчных латинских букв. Найдите количество пар непересекающихся подстрок-палиндромов этой строки.

Более формально: найдите количество четверок (a, b, x, y) таких, что 1 ≤ a ≤ b < x ≤ y ≤ |s| и подстроки s[a... b], s[x... y] являются палиндромами.

Палиндромом называется строка, которая одинаково читается слева направо и справа налево. Например, строки «abacaba», «z», «abba» — палиндромы.

Подстрокой s[i... j] (1 ≤ i ≤ j ≤ |s|) строки s = s1s2... s|s| называется строка, равная sisi + 1... sj. Например, подстрока s[2...4] строки s = «abacaba» равна «bac».

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

В первой строке записана непустая строка s, состоящая из строчных букв латинского алфавита ('a' ... 'z'). Длина строки s не более 2000 символов.

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

Выведите единственное число — количество пар непересекающихся подстрок-палиндромов заданной строки.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
aa
Выходные данные
1
Входные данные
aaa
Выходные данные
5
Входные данные
abacaba
Выходные данные
36