Count Palindromic Substrings

Given a string \(S\) of length \(n\) (where \(1 \le n \le 1000\)) consisting only of lowercase English letters, your task is to count all palindromic substrings in \(S\). A substring is a contiguous sequence of characters from \(S\). Note that every single character is considered a palindrome. A palindromic substring is one that reads the same forwards and backwards.

Example: For the input string "abba", the palindromic substrings are: "a", "b", "b", "a", "bb", "abba". Thus, there are 6 palindromic substrings in total.

The counting approach can be based on expanding around each possible center of the palindrome. For each index, consider it as the center of an odd-length palindrome and also consider the gap between two characters as the center of an even-length palindrome.

inputFormat

The input consists of a single line, containing the string \(S\) (1 ≤ \(n\) ≤ 1000) composed of lowercase English letters.

outputFormat

Output a single integer, representing the total count of palindromic substrings in \(S\).

a

1