Дана непустая строка 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 = s₁s₂... s_|s| называется строка, равная s_is_i + 1... s_j. Например, подстрока s[2...4] строки s = «abacaba» равна «bac».