Count Palindromic Substrings

You are given a string s. Your task is to count the number of palindromic substrings in s. A substring is a contiguous sequence of characters within the string, and a palindromic substring reads the same backward as forward.

For example, given s = "aba", the palindromic substrings are "a" (first character), "b", "a" (last character), and "aba" itself, making a total of 4.

The mathematical formulation of a palindromic substring can be expressed as follows: \[ \text{For a substring } s[i \dots j], \text{ it is palindromic if } s[i \dots j] = s[j \dots i] \] where \(0 \leq i \leq j < n\) and \(n\) is the length of the input string.

inputFormat

The input consists of a single line that contains the string s. The string can be assumed to have a small length suitable for an O(n²) solution.

outputFormat

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

a

1