Distinct Palindromic Substrings

You are given a string s. Your task is to count the number of distinct palindromic substrings contained in s. A palindrome is a string that reads the same forwards and backwards. Formally, a string t is a palindrome if \(t = t^R\), where \(t^R\) denotes the reverse of t in \(\LaTeX\) format.

Example:

• For s = "abba", the distinct palindromes are: "a", "b", "bb", "abba". Hence, the output is 4.

Note that substrings are extracted from contiguous segments of the string, and even if palindromic substrings overlap, they are counted only once if they are identical.

inputFormat

The input consists of a single line containing the string s (with no leading or trailing spaces).

outputFormat

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

abba

4