cho.sh

Counting Palindromes (Small)

Count how many subsequences of a string of length up to 30 are palindromes, treating subsequences that use different positions as distinct.

Medium7Dynamic programmingStringCombinatoricsImplementationInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

A palindrome is a word that reads the same forwards and backwards. Words such as 'aba' and 'a' are palindromes, while 'abaccbcb' and 'anavolimilana' are not.

Seungsu wants to know how many subsequences of a given string are palindromes. The empty subsequence is not counted. Subsequences are distinguished by the set of positions chosen, so two subsequences that spell the same letters from different positions count as different subsequences.

For example, the subsequences of 'abb' are 'a', 'b', 'b', 'ab', 'ab', 'bb', and 'abb'. Among them, the palindromes are 'a', 'b', 'b', and 'bb', so there are 4.

Given a string, write a program that prints the number of its subsequences that are palindromes.

Input

The first line contains a string SS. The length of SS is between 1 and 30, inclusive, and SS consists only of lowercase English letters.

Output

Print the number of subsequences of SS that are palindromes.