Дана непустая строка 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».
Выходные данные
Выведите единственное число — количество пар непересекающихся подстрок-палиндромов заданной строки.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.