e-olymp
Competitions

Azerbaijan Programming Olympiad - 2nd Stage preparation

Super palindromes

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.

Input

One string S contains a sequence of length from 1 to 1000 lowercase Latin letters without spaces.

Output

Print one number - the number of substrings of S that are super palindromes.

Time limit 1 second
Memory limit 128 MiB
Input example #1
abc
Output example #1
0
Input example #2
abacdc
Output example #2
3
Author Pavel Kuzhnecov