fateice loves strings, especially double-palindrome strings.

If you do not know what a double-palindrome string is, a string $s$ is a double-palindrome string if and only if there exist non-empty palindrome strings $a$ and $b$ such that $s$ is formed by concatenating $a$ and $b$. For example, $aabcb$ is a double-palindrome string, while $aba$ is not.

One day, fateice saw a fresh string $s$. He listed all distinct substrings of $s$ and counted how many of them are double-palindrome strings. Two strings are considered distinct if and only if they have different lengths or there exists an index where the characters at the corresponding positions are different.

fateice quickly reported the answer, but he wants to test you.

Input

Read from standard input.

A single non-empty string $s$. It is guaranteed to consist of lowercase letters.

Output

Output to standard output.

Output a single integer representing the number of distinct double-palindrome substrings in $s$.

Examples

Input 1

abbbab

Output 1

11

Note 1

The distinct double-palindrome substrings in $s$ are: ab, abb, abbb, abbbab, ba, bb, bba, bbab, bbb, bbba, bbbab, totaling 11.

Input 2

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Output 2

233

Note 2

Anyone with a little common sense...

Input 3

abbbbaaabbbabbabbbabaababbaaababbcbbbbbaabbcbbaabbaabbbbabaabbbabbbbbaaaaabbbbbcbbbbababcaabbabcabbabaaababbbaaaabbcbcbaabbbbbabbbbbaababaababaaaabbbabaabbabaacaabaaaababbaaaaababbbbbabbaabbaabbaaabbbabaabbabaaabbabaabbbbbbababcaabbabababbbbbabbaaaaacbbaabbbaabbacbbbaacabbbabcaacbbbabaaaabbbaaababbb

Output 3

614

Note 3

I have a marvelous explanation, but the space here is too small to contain it.

Constraints

For all data, $1 \leq |s| \leq 5 \times 10^5$.

There are 6 subtasks. The special constraints and scores for each subtask are as follows:

1. (10 points) $|s| \leq 300$.
2. (20 points) $|s| \leq 5000$.
3. (20 points) $|s| \leq 40000$.
4. (20 points) $|s| \leq 1.5 \times 10^5$.
5. (10 points) $s$ consists only of $\{a, b\}$ and each character is chosen uniformly at random from $\{a, b\}$.
6. (20 points) No additional constraints.