Description

Although little $a$ is a science student, he often calls himself a true liberal arts student. For some reason, he has a strange love for recitation, which also led him to the biology contest, known for its heavy memorization. However, he soon found that this still could not satisfy his passion for reciting, but as a strong OIER, he found a method—reciting gene sequences. Yet this is too hard, and little $a$ felt overwhelmed.

He found that if he could know in advance how many pairs of disjoint palindromic substrings there are in the sequence, he might discover a trick for memorization. To further test this idea, little $a$ decided to choose a string $SS$ consisting of lowercase letters for experimentation. Since there were too many disjoint palindromic substrings, he quickly got dizzy counting them. But he believes this problem is a piece of cake for you.

1. For the string $SS$, let its length be $\text{Len}$. We use $S_i$ to denote the $i$-th character of $SS$ ($1 \le i \le \text{Len}$).

2. $S[i,j]$ denotes a substring of $SS$, where $S[i,j] = S_i S_{i+1} S_{i+2} \cdots S_{j-2} S_{j-1} S_{j}$. For example, when $SS$ is abcgfd, $S[2,5]$ is bcgf, and $S[1,5]$ is abcgf.

3. A string is called a palindrome if and only if the string is the same when reversed, such as abcba.

4. Consider a quadruple $(l,r,L,R)$. If both $S[l,r]$ and $S[L,R]$ are palindromes, and $1 \le l \le r < L \le R \le \text{Len}$ holds, then we call $S[l,r]$ and $S[L,R]$ a pair of disjoint palindromic substrings. This problem asks for the number of such quadruples. Two quadruples are the same if and only if the corresponding $l,r,L,R$ are all the same.

Input Format

The input consists of a single line: the string $SS$, guaranteed to contain only lowercase letters, ending with a newline.

50% of the testdata satisfies that the length of $SS$ does not exceed $200$; 100% of the testdata satisfies that the length of $SS$ does not exceed $2000$.

Output Format

Output a single line containing one integer: the number of pairs of disjoint palindromic substrings.

aaa

5

Hint

[Sample explanation]

When $SS = \text{"aaa"}$, every substring of $SS$ is a palindrome. There are 5 pairs of disjoint palindromic substrings in total: $(1,1,2,2)$, $(1,1,2,3)$, $(1,1,3,3)$, $(1,2,3,3)$, $(2,2,3,3)$.

Translated by ChatGPT 5