A genomics tool scans a strand written as a string of lowercase English letters and needs to know how many distinct palindromic patterns it contains. Count the number of distinct non-empty substrings that read the same forward and backward. Two occurrences of the same substring value are counted only once.
Input format
Line 1: a non-empty string of lowercase English letters.
Output format
A single integer: the number of distinct non-empty palindromic substrings.
Constraints
- 1 <= length of the string <= 3000
- The string consists only of lowercase English letters (
a-z).