Count Distinct Palindromic Substrings

You are given a string s consisting of lowercase English letters. Your task is to count the number of distinct palindromic substrings present in s.

A palindrome is a string that reads the same backward as forward. For example, "abba" is a palindrome while "abc" is not. A substring is a contiguous sequence of characters within a string.

Note that the empty string is not considered a palindromic substring.

Example:

Input: abba
Output: 4
Distinct palindromic substrings are: "a", "b", "bb", "abba"

</p>

inputFormat

The input consists of a single line containing the string s. The string will contain only lowercase English letters. It may also be empty.

It is read from the standard input (stdin).

outputFormat

Output a single integer representing the number of distinct palindromic substrings in s. This number should be printed to the standard output (stdout).

## sample

abba

4