e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic programming

Palindromes

Non-empty string containing a certain word is called palindrome if it reads the same from left to right and from right to left.

Let we are given a word s, consisting of n uppercase letters of Latin alphabet. Deleting from the word a certain set of characters, you can get the palindrome string. Find the number of ways to delete from the word some (possibly empty) set of symbols so that the resulting string is a palindrome. Ways in different order of deleting characters are considered equal.

Input

One string s of length n (1n60).

Output

Print the number of ways to get a palindrome.

Time limit 1 second
Memory limit 128 MiB
Input example #1
BAOBAB
Output example #1
22