Count Palindromic Substrings

You are given a string s consisting only of lowercase alphabets. Your task is to count the number of substrings of s that are palindromes.

A palindrome is a string that reads the same backward as forward. Note that every single character is considered a palindrome. In addition, a substring is a contiguous block of characters within the string.

The number of palindromic substrings can be computed by iterating over all possible centers (which can be an actual character or between two characters) and expanding outward while the substring remains a palindrome. Mathematically, if the length of the string is n, there are 2n-1 potential centers. For each center, we expand using the following formula:

\( \text{left} = \lfloor \frac{center}{2} \rfloor \quad \text{and} \quad \text{right} = \lfloor \frac{center}{2} \rfloor + (center \mod 2) \)

Count every valid palindrome found during the expansion.

inputFormat

The input consists of a single line containing a string s which only contains lowercase alphabets.

outputFormat

Output a single integer representing the total number of palindromic substrings in s.## sample

abba

6