Palindromic Substrings

Count all palindromic substrings; substrings with the same characters but different start or end positions are counted separately. The first sentence of the source is truncated; this definition is made clear by the title and by the example in which aaa lists six positional substrings.

输入格式

One line with a lowercase string of length 1..1000.

输出格式

Output a single integer answer.

样例 1

输入：

abc

输出：

3

样例 2

输入：

aaa

输出：

6

样例 3

输入：

abba

输出：

6

样例说明

Example 1: three single characters, 3 in total. Example 2: three a, two aa and one aaa, 6 in total. Example 3: four single characters plus bb and abba, 6 in total.