A substring is a palindrome when it reads the same left-to-right and right-to-left. Given a string, count how many of its substrings are palindromes. Two substrings that occupy different index ranges are counted separately even if they contain the same characters, so every single character contributes one palindrome.
Input format
A single line containing the string, made up of lowercase English letters.
Output format
A single integer: the number of substrings (counted by their start and end positions) that are palindromes.
Constraints
- The string length n satisfies 1 <= n <= 2000.
- The string contains only lowercase letters
a-z.