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
sfialok98: 2017-06-27 13:50:47

Nice problem..
Learned Palindromic tree..

Gaurav Dahima: 2016-08-31 20:25:28

O(n*n) passes, try MSUBSTR (a bit harder) after this.

Piyush Kumar: 2016-07-05 14:22:19

O(n) solution can survive better constraints! :)

minhthai: 2016-04-05 16:25:36

if u find it difficult, read the problem again :)

[Mayank Pratap]: 2016-03-02 09:24:25

Simple Memoisation :)

sandy: 2016-02-26 08:28:58

nice problem to try out palindromic tree :)

Sumit Vohra: 2016-01-18 19:59:43

0.0 manacher's rox

vinayawsm: 2014-03-23 11:49:06

Last edit: 2016-10-03 22:37:01
achiever202: 2013-07-09 08:27:37

will the initial string be a palindrome ??

Juɑƞ Chɑpɑrro: 2013-05-19 19:48:00

imput:
a
aa
aaa
aaaa
output:
1
3
6
10

Last edit: 2013-03-29 02:23:00

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