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 (1 ≤ n ≤ 60).

Output

Print the number of ways to get a palindrome.