Count Different Palindrome Substrings

Given a string s consisting only of lowercase English letters, count the occurrences of all non-empty contiguous palindromic substrings. Different index ranges are counted separately, even if their contents are the same.

输入格式

One line containing a lowercase string s; LF or CRLF line endings are supported, and the trailing newline may be omitted. The line ending is not part of the string. This site covers the full string domain within the existing 32MiB per-case input budget, without borrowing another problem's site-specific length limit. Without a trailing newline there may be 33554432 letters. An empty line denotes the empty string, a mathematical extension by this site.

输出格式

Output the exact integer, without taking a modulus; the original Java int interface is too narrow for the full domain, so this site explicitly counts with 64-bit arithmetic. Output 0 for the empty string.

样例 1

输入：

hellolle

输出：

13

样例 2

输入：

wowpurerocks

输出：

14

样例 3

输入：

aaa

输出：

6

样例说明

In the original hellolle there are 8 single characters, two ll at different positions, lol, lloll, and ellolle, 13 in total; wowpurerocks has 12 single characters plus wow and rer, 14 in total. The original text explicitly states that the two ll are at different positions, so substrings are not deduplicated by content. The third public example aaa→6 was derived by this site.