Practice Strings with the exercise "Palindromic Decomposition"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Strings

Statement

Goal

We say a tuple of three strings (P, Q, R) is a palindromic decomposition of string S if P+Q+R=S and all of P, Q and R are palindrome. Note that P, Q and R can be the empty string ε.

Given string S, calculate the number of the palindromic decompositions of S.

For example, if you are given abab, you should answer 6 because (ε, a, bab), (ε, aba, b), (a, ε, bab), (a, bab, ε), (aba, ε, b) and (aba, b, ε) are the palindromic decompositions of abab.

Input

A string S.

Output

The number of palindromic decompositions of S.

Constraints

1 ≤ length of S ≤ 4000.
S is consisting of lowercase English letters.

Example

Input

abab

Output

Solve it

A higher resolution is required to access the IDE