Strings that read the same from left to right and right to left are called palindromes (radar, madam, or racecar).
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.