Counting Palindromic Substrings

You are given a string s. Your task is to calculate the total number of palindromic substrings present in s. A substring is considered palindromic if it reads the same backward as forward. Formally, a substring s[i...j] is a palindrome if:

$s[i...j]=s[i...j]^R$

where $s[i...j]^R$ represents the reverse of the substring $s[i...j]$. Note that substrings with different start or end indices are counted separately even if they consist of the same sequence of characters.

inputFormat

The input is read from standard input. It consists of a single line containing the string s.

outputFormat

Output to standard output a single integer representing the total number of palindromic substrings in the given string.

ababa

9