Count Distinct Palindromic Substrings

Count the palindromic substrings with distinct text; multiple occurrences count only once. The correct answer for the long original OCR example abcddcbabcdcdaadcdcbabcddcb is 26, not 27; the original enumeration contains duplicates and substrings that do not exist.

输入格式

One line containing a lowercase string; complete OCR range 1≤length≤5000.

输出格式

Output a single integer, the answer.

样例 1

输入：

mokkori

输出：

7

样例 2

输入：

aabaa

输出：

5

样例 3

输入：

abcddcbabcdcdaadcdcbabcddcb

输出：

26

样例说明

The outputs of the three public examples are, in order: 7; 5; 26. These answers were verified by independent enumeration or direct simulation.