Count Palindromic Substrings

Given a string s, count the total number of palindromic substrings in it. A substring is defined as a contiguous sequence of characters within the string. A palindrome is a string that reads the same forwards and backwards, i.e., it satisfies the condition \(s = s^R\), where \(s^R\) is the reverse of \(s\).

Your task is to implement an efficient algorithm to count all palindromic substrings. For example, the string "abba" has 6 palindromic substrings: "a", "b", "b", "a", "bb", "abba".

inputFormat

The input consists of a single line containing the string s (with no spaces) for which you need to count the palindromic substrings.

outputFormat

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

abba

6