Count Palindromic Substrings

You are given a string s. Your task is to count the number of palindromic substrings in s.

A palindrome is a string that reads the same backward as forward. In other words, a substring s[l...r] (with 0 ≤ l ≤ r < n, where n is the length of s) is a palindrome if it satisfies the condition:

$$\forall\, k \in \{0,1,\dots, r-l\},\quad s[l+k] = s[r-k] $$

For example:

• For s = "abc", the palindromic substrings are: "a", "b", "c" (total = 3).
• For s = "aaa", the palindromic substrings are: "a", "a", "a", "aa", "aa", "aaa" (total = 6).

The input string may contain mixed case letters and could be empty. Your solution should read input from the standard input and produce output to the standard output.

inputFormat

The input is provided via stdin and consists of a single line containing the string s. The length of s is between 0 and 10³ characters.

outputFormat

Output a single integer to stdout representing the total number of palindromic substrings in the given string s.

## sample

abc

3