Algorithms and Data Structures

Palindromes

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.

Examples

Input
Output
BAOBAB
22

Explanation

  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
 

Constraints

Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in