CF159D.Palindrome pairs

You are given a non-empty string s consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (a, b, x, y) such that 1 ≤ a ≤ b < x ≤ y ≤ |s| and substrings s[a... b], s[x... y] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring s[i... j] (1 ≤ i ≤ j ≤ |s|) of string s = _s_1_s_2... s|s| is a string s__i__s__i + 1... s__j. For example, substring s[2...4] of string s = "abacaba" equals "bac".

给你一个非空字符串 $s$，它仅由小写字母组成。请找出该字符串中所有不重叠的回文子串对的数量。

更形式化地说，你需要计算满足以下条件的四元组 $(a,\,b,\,x,\,y)$ 的数量：

$$1 \le a \le b < x \le y \le |s|$$

且子串 $s[a\ldots b]$ 与 $s[x\ldots y]$ 均为回文串。

回文串是指从左到右读和从右到左读完全相同的字符串。例如，“abacaba”、“z”、“abba” 都是回文串。

字符串 $s = s_1s_2\ldots s_{|s|}$ 的子串 $s[i\ldots j]$（其中 $1 \le i \le j \le |s|$）定义为字符串 $s_is_{i+1}\ldots s_j$。例如，当 $s =$ “abacaba” 时，其子串 $s[2\ldots 4]$ 等于 “bac”。

The first line of input contains a non-empty string s which consists of lowercase letters ('a'...'z'), s contains at most 2000 characters.

输入的第一行包含一个非空字符串 $s$，该字符串由小写字母（'a'...'z'）组成，且 $s$ 的长度最多为 2000 个字符。

Output a single number — the quantity of pairs of non-overlapping palindromic substrings of s.

Please do not use the %lld format specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d format specifier.

输出一个整数——字符串 $s$ 中互不重叠的回文子串对的数量。

在 C++ 中，请勿使用 %lld 格式说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。