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).

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

  2. BAOBAB

  3. BAOBAB

  4. BAOBAB

  5. BAOBAB

  6. BAOBAB

  7. BAOBAB

  8. BAOBAB

  9. BAOBAB

  10. BAOBAB

  11. BAOBAB

  12. BAOBAB

  13. BAOBAB

  14. BAOBAB

  15. BAOBAB

  16. BAOBAB

  17. BAOBAB

  18. BAOBAB

  19. BAOBAB

  20. BAOBAB

  21. BAOBAB

  22. BAOBAB

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue