Count Palindromic Substrings

Given a string s, your task is to count the total number of palindromic substrings in s.

A palindromic substring is a substring which reads the same backward as forward. Note that substrings with different start indices are counted as different even if they consist of the same characters.

The solution should efficiently count all valid palindromic substrings. For example, given the input ababa, the answer is 9.

Note: The input string will be provided via standard input (stdin) and the result must be printed to standard output (stdout).

inputFormat

Input is given as a single line from standard input containing the string s.

outputFormat

Output a single integer to standard output which denotes the number of palindromic substrings found in s.

ababa

9