Count Distinct Palindromic Substrings

You are given a string S consisting of lowercase English letters. Your task is to compute the number of distinct palindromic substrings contained in S.

A substring is a contiguous sequence of characters within a string, and a palindrome is a string that reads the same forward and backward. Formally, a string P is a palindrome if it satisfies the condition:

\( P = P^R \)

where \( P^R \) denotes the reversal of P.

For example, for the string "ababa", the distinct palindromic substrings are: "a", "b", "aba", "bab", and "ababa".

Your solution should read the input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

The input consists of a single line containing the string S (possibly empty). There are no extra spaces.

Constraints:

• \( 0 \leq |S| \leq 10^3 \)
• S consists of lowercase English letters only.

outputFormat

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

## sample

ababa

5

</p>