Count Palindromic Substrings

Given a lowercase string s, count all position pairs (i,j) with i≤j such that s[i..j] is a palindrome. Identical content at different positions is counted separately. The second upstream example gives the output for wowyouwin as 14, which conflicts with this definition; counting position by position as the statement defines gives 10, and this site uses 10.

输入格式

One line containing a non-empty string of only a-z. Added by this site: 1≤|s|≤200000.

输出格式

Output the number of palindromic substring occurrences, as a 64-bit integer.

样例 1

输入：

hellolle

输出：

13

样例 2

输入：

wowyouwin

输出：

10

样例 3

输入：

aa

输出：

3