Counting Non-Overlapping Palindromic Pairs

A string S of lowercase letters is given. For the string, let its length be \(n\) and denote by \(S_i\) the \(i\)-th character of \(S\) for \(1 \le i \le n\). For indices \(l\) and \(r\) with \(1 \le l \le r \le n\), let \(S[l,r]\) represent the substring \(S_l S_{l+1} \cdots S_r\). A string is called a palindrome if it reads the same backward as forward (for example, abcba).

We define a quadruple \((l, r, L, R)\) to form a pair of non-overlapping palindromic substrings if both \(S[l,r]\) and \(S[L,R]\) are palindromes and they do not overlap, that is, \(1 \le l \le r < L \le R \le n\). Two quadruples are considered different if any of the indices \(l, r, L, R\) differs.

Your task is to count the total number of such quadruples.

Hint: One efficient approach is to precompute all palindromic substrings using dynamic programming, record the count of palindrome substrings starting at each index, then for every palindromic substring \(S[l, r]\) add the total number of palindromic substrings whose starting index is greater than \(r\). Use \(r+1\) as the beginning of the second palindrome.

inputFormat

The input consists of a single line containing the string S composed of lowercase letters.

outputFormat

Output a single integer representing the number of quadruples \((l, r, L, R)\) such that both \(S[l,r]\) and \(S[L,R]\) are palindromes and \(r < L\).

sample

aba

3