Super palindromes

The palindrome is a string with a length greater than one character that reads the same both from right to left and left to right. A superpalindrome is a string that can be represented as the concatenation of one or more palindromes.

You are given a string $s$. Find the number of substrings in $s$ that are superpalindromes.

Input

The string $s$ that consists of a sequence of lowercase Latin letters with a length from $1$ to $1000$, without spaces.

Output

Print a single integer — the number of substrings of the string $s$ that are superpalindromes.

Examples