The palindrome is a string longer than one character, that reads the same right to left and left to right. The super palindrome is a string that can be represented as a concatenation of one or more palindromes. Given the string $S$. Find the number of substrings in $S$ that are super palindromes. \InputFile One string $S$ contains a sequence of length from $1$ to $1000$ lowercase Latin letters without spaces. \OutputFile Print one number --- the number of substrings of $S$ that are super palindromes.