Counting Palindromic Substrings

Given a string s, count the total number of palindromic substrings within s. A substring is a contiguous sequence of characters within the string. A palindromic substring is one which reads the same backward as forward.

For example, if s = "abba", the palindromic substrings are: "a", "b", "b", "a", "bb", "abba", totaling 6.

The task is to implement an efficient solution that computes this quantity. Note that substrings with different starting or ending positions are considered distinct even if they consist of the same characters.

Mathematical Formula: The total number of substrings of a string of length n is given by \(\frac{n(n+1)}{2}\), but here we only count those which are palindromic.

inputFormat

The input consists of a single line containing the string s whose palindromic substrings are to be counted.

Note: The input is provided via standard input (stdin).

outputFormat

Output a single integer representing the number of palindromic substrings in the input string.

Note: The output should be written to standard output (stdout).

a

1