NUMOFPAL - Number of Palindromes

no tags 

Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "malayalam" can be created by some ways:


* malayalam = m + ala + y + ala + m
* malayalam = m + a + l + aya + l + a + m

We want to take the value of function NumPal(s) which is the number of different palindromes that can be created using the string S by the above method. If the same palindrome occurs more than once then all of them should be counted separately.


Input

The string S.


Output

The value of function NumPal(s).


Limitations

0 < |s| <= 1000


Example


Input:

malayalam

Output:

15


hide comments
Ehor Nechiporenko: 2012-04-06 14:13:59

So problem can be formulated in another way:
How many palindromic substrings does this string contain?
For test input 2 substrings S[1,3] = "ala" and S[5,7]="ala" are different.

[Rampage] Blue.Mary: 2012-04-06 14:13:59

Just outputs the number of palindromic substrings of the input string. (If the same palindrome occurs more than once then all of them should be counted separately.)

The quick brown fox jumps over the lazy dog: 2012-04-06 14:13:59

why it should be 8??????

manmeet: 2012-04-06 14:13:59

Answer should be 8


Added by:The quick brown fox jumps over the lazy dog
Date:2010-10-18
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Udit Agarwal