Problem: Given a string S, count the number of non empty sub strings that are palindromes.
A sub string is any continuous sequence of characters in the string.
A string is said to be palindrome, if the reverse of the string is same as itself.
Two sub strings are different if they occur at different positions in S

Input
Input contains only a single line that contains string S.   

Output
Print a single number, the number of sub strings that are palindromes.

Constraints
1 ≤ |S| ≤ 50
S contains only lower case latin letters, that is characters a to z.

SAMPLE INPUT
dskjkd

SAMPLE OUTPUT
7

Explanation

The 7 sub strings are d, s, k, j, k, d, kjk.

Solution (in PYTHON):

Solution:
from sys import *
def longestPallindrome(seq):
		seqLen = len(seq)
		l = [maxint] * (seqLen*2 + 1)
		nl = [0] * (seqLen*2 + 1)
		i = 0
		k = 0
		palLen = 0
		numPal = 0
		while i < seqLen:
				if i > palLen and seq[i - palLen - 1] == seq[i]:
						palLen += 2
						numPal += 1
						i += 1
						continue
				nl[k] = numPal
				l[k] = palLen
				k+=1
				#l.append(palLen)
				s = k - 2
				e = s - palLen
				flag = False
				for j in xrange(s, e, -1):
						d = j - e - 1
						if l[j] == d and not flag:
								palLen = d
								numPal = nl[j]
								flag = True
								oldk = k
						#l.append(l[j])
						# if d < l[j]:
						# 		l[k] = d
						# 		k+= 1
						# 		#l.append(d)
						# else:
						l[k],nl[k] = min((l[k],nl[k]),(l[j],nl[j]))
						#l[k] = l[j]
						k+= 1
						#l.append(l[j])
						#l.append(min(d, l[j]))
				if not flag:
						palLen = 1
						i += 1
				else:
						k = oldk

		l[k] = palLen
		nl[k] = numPal
		k += 1
		#l.append(palLen)
		lLen = k
		s = lLen - 2
		e = s - (2 * seqLen + 1 - lLen)
		for i in xrange(s, e, -1):
				d = i - e - 1
				l[k],nl[k] = (l[i],nl[i])
				#l[k],nl[k] = min((l[k],nl[k]),(l[i],nl[i]))				
				#l[k] = min(d,l[i])
				k+= 1
				#l.append(min(d, l[i]))
		return l,nl

def main():
		s = raw_input()
		(l,nl) =  longestPallindrome(s)
		print sum(nl) + len(s)
main()