Count Palindromic Substrings

Given a string s, your task is to count all of its palindromic substrings. A substring is a contiguous block of characters in s and a substring is palindromic if it reads the same forwards and backwards. Note that every single character is itself a palindrome.

For a given string s of length n, you are to compute the total number of substrings which satisfy this property. The mathematical formulation can be expressed as:

\[ \text{Count}(s) = \sum_{i=0}^{n-1} \sum_{j=i}^{n-1} [s[i\ldots j] \text{ is a palindrome}] \]

For example, if s = "ababa", the expected output is 9.

inputFormat

The input consists of a single line containing the string s.

Constraints: The string consists of only lowercase English letters and its length is at least 1.

outputFormat

Output a single integer, the total number of palindromic substrings found in s.

a

1