题目描述

给出一个字符串，求字符串所有子串中，回文串的个数。不同位置的子串当做不同的。字符串长度小于等于 $10^5$

输入格式

一行,一个字符串

输出格式

一个整数，回文子串的个数

样例

输入样例

abaabac

输出样例

12