You are given a string $S$. Find the number of ways to choose an unordered pair of non-overlapping non-empty substrings of this string (let's denote them by $s_1$ and $s_2$ in such a way that $s_2$ starts after $s_1$ ends) such that their concatenation $s_1 + s_2$ is a palindrome.
Two pairs $(s_1, s_2)$ and $(s_1', s_2')$ are different if $s_1$ is chosen at a different position from $s_1'$ or $s_2$ is chosen at a different position from $s_2'$.

-----Input-----
The first and only line of the input contains a single string $S$.

-----Output-----
Print a single line containing one integer — the number of ways to choose a valid pair of substrings.

-----Constraints-----
- $1 \le |S| \le 1,000$
- $S$ contains only lowercase English letters

-----Subtasks-----
Subtask #1 (25 points): $|S| \le 100$
Subtask #2 (75 points): original constraints

-----Example Input-----
abba

-----Example Output-----
7

-----Explanation-----
The following pairs of substrings can be chosen: ("a", "a"), ("a", "ba"), ("a", "bba"), ("ab", "a"), ("ab", "ba"), ("abb", "a"), ("b", "b").

见题面

见题面