Count Distinct Palindromic Substrings

Given a string s, count and output the number of distinct palindromic substrings it contains. A substring is a contiguous sequence of characters in s. A palindrome is a string that reads the same backward as forward, i.e., $$ s = s^R $$, where $$ s^R $$ represents the reverse of s. All substrings (including those of length 1) should be considered.

inputFormat

The input consists of a single line containing the string s. The string will be read from standard input.

outputFormat

Output a single integer representing the number of distinct palindromic substrings in the given string. The output should be written to standard output.## sample

abac

4