题目描述

对一个字符串 $S$ ，如果一个字符串四元组 $(A,B,C,D)$ 满足如下条件，就称 $(A,B,C,D)$ 是 $S$ 的一个“公式”：

• $S$ 可以由 $A,B,B,C,D$ 这五个字符串按顺序拼接而成。

• $B$ 不是空串。

• $C$ 是非空回文串。

给定一个只包含小写字母的字符串 $S$ ，求它有多少个不同的“公式”。

输入格式

一行，一个字符串 $S$ 。

输出格式

一行一个整数，表示答案。

样例 #1

aaaaa

7

共有 $7$ 种“公式”：(-,a,a,aa), (a,a,a,a), (aa,a,a,-), (-,a,aa,a), (a,a,aa,-), (-,a,aaa,-), (-,aa,a,-)。

样例 #2

ababccddcc

7

样例 #3 & #4

见下发文件。

数据范围

设 $n$ 为 $S$ 的长度。保证 $1\leq n\leq 2\times 10^5$ 。