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
tuhin: 2013-02-19 16:19:38

Last edit: 2013-03-15 13:48:15
saket diwakar: 2013-01-28 21:48:07

simple one...:)

god_father: 2012-12-19 08:36:50

what should be output for string "aaa"?

David Gómez: 2012-04-06 14:13:59

@Mohamed Maher:
The answer are in the following format:
a b str where substr(s, a, b) = str

0 0 m
0 8 malayalam
1 1 a
1 3 ala
1 7 alayala
2 2 l
2 6 layal
3 3 a
3 5 aya
4 4 y
5 5 a
5 7 ala
6 6 l
7 7 a
8 8 m

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

can some provide some trickier test cases ??
Initial string will always be a palindrome??

Last edit: 2010-10-27 06:32:31
Mohamed Maher: 2012-04-06 14:13:59

can anyone write the 15 palindrome

Radhakrishnan Venkataramani: 2012-04-06 14:13:59

Dont think this s COUNTPAL problem of CODECHEF OCT 10 ..
this s a simpler version of that

sudipto das: 2012-04-06 14:13:59

@manmeet:read the problem carefully...it is not the problem u have assumed..(i had also thought so but later found out it is a different problem....)

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.)


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