Strings that read the same from left to right and right to left are called palindromes (radar, madam, or racecar).
Given a string s, you are asked to tell the number of different ways one can obtain a palindrome from s by removing characters. It’s possible to not remove any character and still obtain a palindrome. The sequence of removing characters does not matter.
Input
The input contains the string s (1 ≤ |s| ≤ 60) which consists of uppercase Latin letters.
Output
The program should print the number of different ways to obtain a palindrome from s.