Migrated from Lutece 2075 本质不同的回文子串个数

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

如题

Input

输入一行，共一个字符串$S,1\leq|S|\leq5\times10^5$。

Output

输出一行，$S$本质不同的回文子串的个数。

Samples

aba

3