Count Palindromic Substrings

Given a string S consisting of lowercase letters, your task is to compute the number of substrings of S that are palindromes.

A substring is a contiguous sequence of characters within the string, and a palindrome is a sequence that reads the same forwards and backwards. Note that every single character is considered a palindrome.

For instance, for the string aaa, the palindromic substrings are: a (first character), a (second character), a (third character), aa (first two characters), aa (last two characters) and aaa (the entire string), which gives a total of 6 palindromic substrings.

The solution should use dynamic programming or any efficient method to compute the result. All input is read via standard input and the result should be printed to standard output.

inputFormat

The input consists of a single line containing a string S composed of lowercase letters only.

Input Format:

S

Here, S is the input string.

outputFormat

Output a single integer representing the number of palindromic substrings found in the input string.

Output Format:

result

Where result is the computed number.

## sample

abc

3