Migrated from Lutece 1551 Hesty Str1ng

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A chrysanthemum was painted on the second page, and we tried to use the magic power learned just now.

The beautiful flower was compacted to a colorful string $S$ representing by characters for some simplifying reasons.

As known, if we try to choose a substring $A$ of $S$ and concatenate it with an arbitrary non-empty string $B$ whose length is less than $A$, we can get a new string $T$.

The poetry told us the key to the eternity living secret is the number of the distinct palindrome strings made by the method above.

Two strings are considered different if and only if there are different characters in the same position of two strings.

Input

Only one line contains the string $S$.

$S$ is composed by lowercase English characters, $1 \leq |S| \leq 100000$.

Output

The key to the eternity living secret.

Samples

abc

3

Note

The palindrome strings can be made are "aba", "bcb", "abcba".

Resources

The 15th UESTC Programming Contest Preliminary