Palindromic Substrings

Count all palindromic substrings; the same text occurring at different positions is counted separately. The original body is truncated, but aaa→6 and its enumeration make this rule clear; it differs from the distinct-text count of problem 4.

输入格式

One line containing a lowercase string; complete original bound 1≤length≤1000.

输出格式

Output a single integer, the answer.

样例 1

输入：

abc

输出：

3

样例 2

输入：

aaa

输出：

6

样例 3

输入：

abba

输出：

6

样例说明

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