Palindrome Counter

Given a string consisting only of lowercase English letters, count the occurrences of palindromic substrings in it. Identical content at different positions is counted separately.

输入格式

A single line containing the string s, of length 1..5000, consisting only of lowercase English letters.

输出格式

Output the number of palindromic substring occurrences.

样例 1

输入：

tacocat

输出：

10

样例 2

输入：

aaa

输出：

6

样例 3

输入：

abccba

输出：

9