NUMOFPAL - Number of Palindromes

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

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

hide comments
2016-01-18 19:59:43 Sumit Vohra
0.0 manacher's rox
2013-07-09 08:27:37 achiever202
will the initial string be a palindrome ??
2013-05-19 19:48:00 Juɑƞ Chɑpɑrro
imput:
a
aa
aaa
aaaa
output:
1
3
6
10

Last edit: 2013-03-29 02:23:00
2013-01-28 21:48:07 saket diwakar
simple one...:)
2012-12-19 08:36:50 god_father
what should be output for string "aaa"?
2012-04-06 14:13:59 David Gómez
@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
2012-04-06 14:13:59 lucky
can some provide some trickier test cases ??
Initial string will always be a palindrome??

Last edit: 2010-10-27 06:32:31
2012-04-06 14:13:59 Mohamed Maher
can anyone write the 15 palindrome
2012-04-06 14:13:59 Radhakrishnan Venkataramani
Dont think this s COUNTPAL problem of CODECHEF OCT 10 ..
this s a simpler version of that
2012-04-06 14:13:59 sudipto das
@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....)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.