Counting Palindromic Substrings

Given a string S, your task is to count the number of palindromic substrings in S. A palindromic substring is defined as a substring that reads the same backward as forward. Note that each single character is considered a palindrome on its own. For a substring S[i...j], it is palindromic if S[i] = S[j] and the substring between them is also a palindrome. This condition can be mathematically expressed as:

\(P(i, j) = 1\) if substring \(S[i...j]\) is a palindrome, otherwise \(P(i, j) = 0\).

Read the input from standard input and output the result to standard output.

inputFormat

The input consists of a single line containing the string S. The length of S is between 1 and 1000, and it consists of lowercase English letters.

outputFormat

Output a single integer representing the total number of palindromic substrings in the given string.## sample

a

1