题目描述

小 $a$ 虽然是一名理科生，但他常常称自己是一名真正的文科生。不知为何，他对于背诵总有一种莫名其妙的热爱，这也促使他走向了以记忆量大而闻名的生物竞赛。然而，他很快发现这并不能满足他热爱背诵的心，但是作为一名强大的 OIER，他找到了这么一个方法——背诵基因序列。然而这实在是太困难了，小啊感觉有些招架不住。

不过他发现，如果他能事先知道这个序列里有多少对互不相交的回文串，他或许可以找到记忆的妙法。为了进一步验证这个想法，小 $a$ 决定选取一个由小写字母构成的字符串 $SS$ 来实验。由于互不相关的回文串实在过多，他很快就数晕了。不过他相信，在你的面前这个问题不过是小菜一碟。

1. 对于字符串 $SS$，设其长度为 Len，那么下文用 $S_i$ 表示 $SS$ 中第 $i$ 个字符（$1 \le i \le Le_n$）。

2. $S[i,j]$ 表示 $SS$ 的一个子串，$S[i,j]=S_i S_{i+1}S_{i+2} \cdots S_{j-2}S_{j-1}S_{j}$，比如当 $SS$ 为 abcgfd 时，$S[2,5]$ 就是 bcgf，$S[1,5]$ 是 abcgf。

3. 当一个串被称为一个回文串当且仅当将这个串反写后与原串相同，如abcba。

4. 考虑一个四元组 $(l,r,L,R)$，当 $S[l,r]$ 和 $S[L,R]$ 均为回文串时，且满足 $1 \le l \le r<L \le R \le \text{Len}$ 时，我们称 $S[l,r]$ 和 $S[L,R]$ 为一对互不相交的回文串。即本题所求，也即为这种四元组的个数。两个四元组相同当且仅当对应的 $l,r,L,R$ 都相同。

输入格式

输入仅一行，为字符串 $SS$，保证全部由小写字母构成，由换行符标志结束。

$50$ ％的数据满足 $SS$ 的长度不超过 $200$；

$100$ ％的数据满足 $SS$ 的长度不超过 $2000$。

输出格式

仅一行，为一个整数，表示互不相关的回文串的对数。

aaa

5

提示

【样例数据说明】

SS="aaa"，SS 的任意一个字符串均为回文串，其中总计有 5 对互不相关的回文串：

(1,1,2,2)，(1,1,2,3)，(1,1,3,3)，(1,2,3,3)，(2,2,3,3)。