Counting Palindromes (Small)

Interview

Time limit2sMemory limit512 MB

Summary

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

Level: Medium7 of 10
Topics: Dynamic programming, String, Combinatorics, Implementation
Solved: No attempts yet

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 $S$ . The length of $S$ is between 1 and 30, inclusive, and $S$ consists only of lowercase English letters.

Output

Print the number of subsequences of $S$ that are palindromes.

Examples1

Example 1
Input
```
abb
```
Expected output
```
4
```